Elementary proof of the transformation formula for Lambert series involving generalized Dedekind sums

An elementary proof is given of the author's transformation formula for the Lambert series $\text{G}{}_{\mathrm{p}}\text{(x) =}\text{Σ}{}_{\mathrm{n?1}}{}^{\mathrm{<mtext>\infty </mtext>}}\text{n}{}^{\mathrm{?p}}\text{x}{}^{\mathrm{n}}\text{(1?x}{}^{\mathrm{n}}\text{)}$ relating G_p(e^2πiτ) to G_p(e^2πiAτ), where p > 1 is an odd integer and $\text{Aτ =}\text{(aτ + b)}\text{(cτ + d)}$ is a general modular substitution. The method extends Sczech's argument for treating Dedekind's function $\text{log}\text{η(τ) =}\text{πiτ}\text{12}\text{? G}{}_1\text{(e}{}^{\mathrm{2\pi i\tau }}\text{)}$, and uses Carlitz's formula expressing generalized Dedekind sums in terms of Eulerian functions.     

Petites valeurs de la fonction d'Euler

Let φ be the Euler's function. A question of Rosser and Schoenfeld is answered, showing that there exists infinitely many n such that $\text{n}\text{φ(n)}\text{> e}{}^{\mathrm{y}}\text{log log}\text{n}$, where γ is the Euler's constant. More precisely, if N_k is the product of the first k primes, it is proved that, under the Riemann's hypothesis, $\text{N}{}_{\mathrm{k}}\text{φ(N}{}_{\mathrm{k}}\text{)}\text{> e}{}^{\mathrm{y}}\text{log log}\text{N}{}_{\mathrm{k}}$ holds for any k ≥ 2, and, if the Riemann's hypothesis is false this inequality holds for infinitely many k, and is false for infinitely many k.     

Coding theory in white Gaussian channel with feedback

The message m = {m(t)} is a Gaussian process that is to be transmitted through the white Gaussian channel with feedback: $\text{Y(t) = ∫}{}_0{}^{\mathrm{t}}\text{F(s, Y}{}_0{}^{\mathrm{s}}\text{, m)ds + W(t)}$. Under the average power constraint, $\text{E[F}{}^2\text{(s, Y}{}_0{}^{\mathrm{s}}\text{, m)] ≤ P}{}_0$, we construct causally the optimal coding, in the sense that the mutual information I_t(m, Y) between the message m and the channel output Y (up to t) is maximized. The optimal coding is presented by $\text{Y(t) = ∫}{}_0{}^{\mathrm{t}}\text{A(s)[m(s) ?}\text{m}\text{?}\text{(s)] ds + W(t)}$, where $\text{m}\text{?}\text{(s) = E[m(s) ¦ Y(u), 0 ≤ u ≤ s]}$ and A(s) is a positive function such that $\text{A}{}^2\text{(s) E |m(s) ?}\text{m}\text{?}\text{(s)|}{}^2\text{= P}{}_0$.     

Generalization of Fenchel's duality theorem for convex vector optimization

For a vector-valued function f, Sup f and Inf f are defined from the Yu's domination theory and the Pareto's efficiency. A notion of conjugate is proposed for convex vector-valued function, this construction gives once more the usual conjugate function: $\text{f}{}^1\text{(x}{}^1\text{) =}\text{sup}\text{[〈x}{}^1\text{, x〉 ? f(x)]}$ when the function f is scalar. Then, this concept is used to write the Fenchel's problem in convex multiple objective optimization and to prove the associated duality theorem.     

Zeta matrices of elliptic curves

Let $\text{O =}\text{lim}{}_{\mathrm{n}}\text{Z/p}{}^{\mathrm{n}}\text{Z}$, let $\text{A}\text{= O[g}{}_2\text{, g}{}_3\text{]}{}_{\mathrm{\Delta }}$, where g₂ and g₃ are coefficients of the elliptic curve: Y² = 4X³ ? g₂X ? g₃ over a finite field and Δ = g₂³ ? 27g₃² and let $\text{B}\text{=}\text{A}\text{[X, Y]}\text{(Y}{}^2\text{? 4X}{}^3\text{+ g}{}_2\text{X + g}{}_3\text{)}$. Then the p-adic cohomology theory will be applied to compute explicitly the zeta matrices of the elliptic curves, induced by the pth power map on the free $\text{A}{}^2\text{?}{}_{\mathrm{Z}}\text{Q}$-module $\text{H}{}^1\text{(X,}\text{A}{}^2\text{?}{}_{\mathrm{Z}}\text{Q)}$. Main results are; Theorem 1.1: X²dY and YdX are basis elements for $\text{H}{}^1\text{(}\text{X}\text{, Γ}{}_{\mathrm{<mtext>A</mtext>}}{}^1\text{(}\text{X}\text{)}{}^2\text{?}{}_{\mathrm{Z}}\text{Q)}$; Theorem 1.2: YdX, X²dY, Y^?1dX, Y^?2dX and XY^?2dX are basis elements for $\text{H}{}^1\text{(}\text{X}\text{? (Y = 0), Γ}{}_{\mathrm{<mtext>A</mtext>}}{}^1\text{(}\text{X}\text{)}{}^2\text{?}{}_{\mathrm{Z}}\text{Q)}$, where $\text{X}$ is a lifting of X, and all the necessary recursive formulas for this explicit computation are given.     

Duality of infinite graphs

Some basic results on duality of infinite graphs are established and it is proven that a block has a dual graph if and only if it is planar and any two vertices are separated by a finite edge cut. Also, the graphs having predual graphs are characterized completely and it is shown that if $\text{G}{}^1$ is a dual and predual graph of G, then G and $\text{G}{}^1$ can be represented as geometric dual graphs. The uniqueness of dual graphs is investigated, in particular, Whitney's 2-isomorphism theorem is extended to infinite graphs. Finally, infinite minimal cuts in dual graphs are studied and the characterization (in terms of planarity and separation properties) of the graphs having dual graphs satisfying conditions on the infinite cuts, as well, is included.     

Fast algorithms for generating all maximal independent sets of interval,circular-arc and chordal graphs

In this paper we give fast algorithms for generating all maximal independent sets of three special classes of graphs—interval, circular-arc, and chordal graphs. The worst-case running times of our algorithms are O(n² + β) for interval and circular-arc graphs, and $\text{O((n + e)}{}^1\text{α)}$ for chordal graphs, where n, e, and α are the numbers of vertexes, edges, and maximal independent sets of a graph, and β is the sum of the numbers of vertexes of all maximal independent sets. Our algorithms compare favorably with the fastest known algorithm for general graphs which has a worst-case running time of $\text{O(n}{}^1\text{e}{}^1\text{α)}$.     

On convergence rates and the expectation of sums of random variables

Let X_i be iidrv's and S_n=X₁+X₂+…+X_n. When EX²₁<+∞, by the law of the iterated logarithm $\text{(S}{}_{\mathrm{n}}\text{?α}{}_{\mathrm{n}}\text{)}\text{(n log n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{→0 a.s.}$ for some constants α_n. Thus the r.v. $\text{Y=sup}{}_{\mathrm{n?1}}\text{[|S}{}_{\mathrm{n}}\text{?α}{}_{\mathrm{n}}\text{|?(δn log n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{]}{}^{\mathrm{+}}$ is a.s.finite when δ>0. We prove a rate of convergence theorem related to the classical results of Baum and Katz, and apply it to show, without the prior assumption EX²₁<+∞ that EY^h<+∞ if and only if $\text{E}\text{|X}{}_1\text{|}{}^{\mathrm{2+h}}\text{[log|X}{}_1\text{|]}{}^{-1}\text{<+∞}$ for 0<h<1 and δ> $\text{h}\text{E}\text{(X}{}_1\text{?}\text{E}\text{X}{}_1\text{)}{}^2$, whereas $\text{E}\text{Y}{}^{\mathrm{h}}\text{=+∞}$ whenever h>0 and $\text{0<δ<h}\text{E}\text{(X}{}_1\text{?}\text{E}\text{X}{}_1\text{)}{}^2$.     

A Dunford-Pettis theorem for L1H∞⊥

The spaces in the title are associated to a fixed representing measure m for a fixed character on a uniform algebra. It is proved that the set of representing measures for that character which are absolutely continuous with respect to m is weakly relatively compact if and only if each m-negligible closed set in the maximal ideal space of L^∞ is contained in an m-negligible peak set for H^∞. J. Chaumat's characterization of weakly relatively compact subsets in $\text{L}{}^1\text{H}{}^{\mathrm{\infty \perp }}$ therefore remains true, and $\text{L}{}^1\text{H}{}^{\mathrm{\infty \perp }}$ is complete, under the first conditions. In this paper we also give a direct proof. From this we obtain that $\text{L}{}^1\text{H}{}^{\mathrm{\infty \perp }}$ has the Dunford-Pettis property.     

Enumeration of self-complementary structures

For functions f : D → R_k where D is a finite set and R_k = {0,1,… k} we define complementary and self-complementary functions. De Bruijn's generalization of Polya's theorem gives a formula for the number of non-isomorphic self-complementary functions $\text{f ∈ R}{}_{\mathrm{k}}{}^{\mathrm{D}}$. We consider the special cases of generalized graphs and m-placed relations. Among other results we prove that the number of non-isomorphic self-complementary relations over 2n elements is equal to the number of non-isomorphic self-complementary graphs with 4n + 1 points.     

Spectral theory of commuting self-adjoint partial differential operators

Let Ω denote a connected and open subset of $\text{R}$ⁿ. The existence of n commuting self-adjoint operators H₁,…, H_n on $\text{L}{}^2\text{(Ω)}$ such that each H_j is an extension of $\text{−}\text{i∂}\text{∂x}{}_{\mathrm{j}}$ (acting on $\text{C}{}_{\mathrm{c}}{}^{\mathrm{\infty }}\text{(Ω))}$ is shown to be equivalent to the existence of a measure μ on $\text{R}$ⁿ such that f → $\text{}\text{̂}$tf (the Fourier transform of f) is unitary from $\text{L}{}^2\text{(Ω)}$ onto Ω. It is shown that the support of μ can be chosen as a subgroup of $\text{R}$ⁿ iff H₁,…, H_n can be chosen such that the unitary groups generated by H₁,…, H_n act multiplicatively on $\text{L}{}^2\text{(Ω)}$. This happens iff Ω (after correction by a null set) forms a system of representatives for the quotient of $\text{R}$ⁿ by some subgroup, i.e., iff Ω is essentially a fundamental domain.     

Scaling limits of Gaussian vector fields

For Gaussian vector fields {X(t) ∈ Rⁿ:t ∈ R^d} we describe the covariance functions of all scaling limits Y(t) = $\text{L}$lim_α↓0 B^?1(α) X(αt) which can occur when B(α) is a d × d matrix function with B(α) → 0. These matrix covariance functions $\text{r(t, s) = EY(t) Y}{}^1\text{(s)}$ are found to be homogeneous in the sense that for some matrix L and each α > 0, $\text{(}{}^1\text{) r(αt, αs) = α}{}^{\mathrm{L1}}\text{r(t, s) α}{}^{\mathrm{L}}$. Processes with stationary increments satisfying (¹) are further analysed and are found to be natural generalizations of Lévy's multiparameter Brownian motion.     

Calcul fonctionnel sur les opérateurs admissibles et application

Let $\text{H}{}_{\mathrm{v}}\text{(h) = ?(}\text{h}{}^2\text{2}\text{) · Δ + V,}\text{lim}{}_{\mathrm{¦x¦\; \to \; +\infty }}\text{V(x) = + ∞}$. Under suitable conditions we prove that $\text{?(H}{}_{\mathrm{v}}\text{(h))}$ is a pseudodifferential operator whose symbol has an asymptotic: $\text{a}{}_{\mathrm{?}}\text{(h) ~∑}{}_{\mathrm{j\; ?\; 0}}\text{h}{}^{\mathrm{j}}\text{a}{}_{\mathrm{?,j}}$. More general pseudodifferential operator's classes are also considered. We apply this result to study the semi-classical behaviour of the spectrum of H_v as h → 0. So, we improve recent results obtained by J. Chazarain and by the author in collaboration with B. Helffer. Furthermore we give a precise meaning to the formal development considered in B. Grammaticos and A. Voros' work (Ann. Physics123 (1979), 359–380).     

On the trace of finite sets

For a family $\text{T}$ of subsets of an n-set X we define the trace of it on a subset Y of X by T_$\text{T}$(Y) = {F∩Y:F?$\text{T}$}. We say that (m,n) → (r,s) if for every $\text{T}$ with |$\text{T| ?m}$ we can find a Y?X|Y| = s such that |T_$\text{T}$(Y)| ? r. We give a unified proof for results of Bollobàs, Bondy, and Sauer concerning this arrow function, and we prove a conjecture of Bondy and Lovász saying $\text{(?}\text{n}{}^2\text{4}\text{? + n + 2,n)→ (3,7)}$, which generalizes Turán's theorem on the maximum number of edges in a graph not containing a triangle.     

On the secondary zeta-functions

Using summability it is shown that $\text{∑}{}_{\mathrm{n}}\text{?2 (Λ(n) ? 1) n}{}^{\mathrm{<mtext>?</mtext><mtext>1</mtext><mtext>2</mtext>}}\text{(log n)}{}^{\mathrm{?8}}$ defines an entire function in the s-plane. Its asymptotic nature is found and a functional equation relating it to the series $\text{∑{i(}\text{1}\text{2}\text{? p)}}{}^{\mathrm{1?8}}$, Im p = γ > 0,is obtained where p = β + iγ are the nontrivial zeros of Riemann's zeta-function.     

The Fréchet distance between multivariate normal distributions

The Fréchet distance between two multivariate normal distributions having means μ_X, μ_Y and covariance matrices Σ_X, Σ_Y is shown to be given by $\text{d}{}^2\text{= |μ}{}_{\mathrm{X}}\text{? μ}{}_{\mathrm{Y}}\text{|}{}^2\text{+}\text{tr}\text{(Σ}{}_{\mathrm{X}}\text{+ Σ}{}_{\mathrm{Y}}\text{? 2(Σ}{}_{\mathrm{X}}\text{Σ}{}_{\mathrm{Y}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$. The quantity d₀ given by $\text{d}{}_0{}^2\text{=}\text{tr}\text{(Σ}{}_{\mathrm{X}}\text{+ Σ}{}_{\mathrm{Y}}\text{? 2(Σ}{}_{\mathrm{X}}\text{Σ}{}_{\mathrm{Y}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ is a natural metric on the space of real covariance matrices of given order.     

The number of caterpillars

A caterpillar is a tree which metamorphoses into a path when its cocoon of endpoints is removed. The number of nonisomorphic caterpillars with n+4 points is $\text{2}{}^{\mathrm{n}}\text{+ 2}{}^{\mathrm{<mtext>[</mtext><mtext>n</mtext><mtext>2</mtext><mtext>]</mtext>}}$. This neat formula is proved in two ways: first, as a special case of an application of Pólya's enumeration theorem which counts graphs with integer-weighted points; secondly, by an appropriate labeling of the lines of the caterpillar.     

On strings containing all subsets as substrings

Let S_π be the length of a shortest sequence of positive integers which contains every Y ?{1,…,n} as a subsequence of |Y| consecutive terms. We give the following asymptotic estimation: $\text{(}\text{2}\text{πn)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{2}{}^{\mathrm{n}}\text{?S}{}_{\mathrm{n}}\text{?(}\text{2}\text{π)}\text{2}{}^{\mathrm{n}}$. The upper bound is derived constructively.     

A generalization of Turán's theorem to directed graphs

We consider an extremal problem for directed graphs which is closely related to Turán's theorem giving the maximum number of edges in a graph on n vertices which does not contain a complete subgraph on m vertices. For an integer n?2, let T_n denote the transitive tournament with vertex set X_n={1,2,3,…,n} and edge set {(i,j):1?i<j?n}. A subgraph H of T_n is said to be m-locally unipathic when the restriction of H to each m element subset of X_n consisting of m consecutive integers is unipathic. We show that the maximum number of edges in a m-locally unipathic subgraph of T_n is ($\text{q}\text{2}\text{)(m?1)}{}^2\text{+q(m?1)r+?}\text{1}\text{4}\text{r}{}^2\text{?}$ where n= q(m?1+r and $\text{?}\text{1}\text{2}\text{(m?1)??r<?}\text{3}\text{2}\text{(m?1)?}$. As is the case with Turán's theorem, the extremal graphs for our problem are complete multipartite graphs. Unlike Turán's theorem, the part sizes will not be uniform. The proof of our principal theorem rests on a combinatorial theory originally developed to investigate the rank of partially ordered sets.