Cogrowth and amenability of discrete groups

Let G be a group and g₁,…, g_t a set of generators. There are approximately (2t ? 1)ⁿ reduced words in g₁,…, g_t, of length ?n. Let $\text{}\text{?}\text{gg}{}_{\mathrm{n}}$ be the number of those which represent 1_G. We show that $\text{γ =}\text{lim}{}_{\mathrm{n\; \to \; \infty }}\text{(}\text{}\text{?}\text{gg}{}_{\mathrm{n}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}$ exists. Clearly 1 ? γ ? 2t ? 1. $\text{η =}\text{(}\text{log}\text{γ)}\text{(}\text{log}\text{(2t ? 1))}$ is the cogrowth. 0 ? η ? 1. In fact $\text{η ∈ {0} ∪ (}\text{1}\text{2}\text{, 1¦}$. The entropic dimension of G is shown to be 1 ? η. It is then proved that d(G) = 1 if and only if G is free on g₁,…, g_t and d(G) = 0 if and only if G is amenable.     

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.     

On total matching numbers and total covering numbers of complementary graphs

Best upper and lower bounds, as functions of n, are obtained for the quantities $\text{β}{}_2\text{(G)+β}{}_2\text{(}\text{G}\text{?}\text{)}$ and $\text{α}{}_2\text{(G)+α}{}_2\text{(}\text{G}\text{?}\text{)}$, where β₂(G) denotes the total matching number and α₂(G) the total covering number of any graph G with n vertices and with complementry graph ?.The best upper bound is obtained also for α₂(G)+β₂(G), when G is a connected graph.     

A periodicity lemma in linear diophantine analysis

Let g = (g₁,…,g_r) ≥ 0 and h = (h₁,…,h_r) ≥ 0, g_?, h_? ∈ $\text{J}$, be two vectors of nonnegative integers and let λ ? $\text{J}$, λ ≥ 0, λ ≡ 0 mod d, where d denotes g.c.d. (g₁,…,g_r). Define

$\text{Δ(λ)=Δ(λg,h):=}\text{min}\text{∑}\text{?=1}\text{r}\text{x}{}_{\mathrm{?}}\text{h}{}_{\mathrm{?}}\text{:x}{}_{\mathrm{?}}\text{?0,x}{}_{\mathrm{?}}\text{∈J,}\text{∑}\text{?=1}\text{?}\text{x}{}_{\mathrm{?}}\text{g}{}_{\mathrm{?}}\text{=λ}$

It is shown in this paper that Λ(λ) is periodic in λ with constant jump. If i? {1,…,r} is such that

$\text{det}\text{g}{}_{\mathrm{i}}\text{h}{}_{\mathrm{i}}\text{g}{}_{\mathrm{?}}\text{h}{}_{\mathrm{?}}\text{? (?1,…r)}$

then

$\text{Δ(λ)+g}{}_{\mathrm{i}}\text{Δ(λ)+h}{}_{\mathrm{i}}$

holds true for all sufficiently large λ, λ ≡ 0 mod d.     

A homomorphic characterization of regular languages

Every regular language R (over any alphabet) can be represented in the form $\text{R = h}{}_4\text{h}{}^{\mathrm{?1}}{}_3\text{h}{}_2\text{h}{}^{\mathrm{?1}}{}_1\text{(110)}$ where h₁, h₂, h₃, and h₄ are homomorphisms. Furthermore, if n is sufficiently large, then $\text{R = g}{}_3\text{g}{}^{\mathrm{?1}}{}_2\text{g}{}_1\text{({1, …, n}10)}$ where, g₁, g₂, and g₃ are homomorphisms.     

Periodic-type functionals and their extensions

Let Ω denote a simply connected domain in the complex plane and let $\text{K[Ω]}$ be the collection of all entire functions of exponential type whose Laplace transforms are analytic on Ω′, the complement of Ω with respect to the sphere. Define a sequence of functionals $\text{{L}{}_{\mathrm{n}}\text{}}\text{on}\text{K[Ω]}$ by $\text{L}{}_{\mathrm{n}}\text{(f) =}\text{1}\text{2πi}\text{∝}{}_{\mathrm{\Gamma }}\text{g}{}_{\mathrm{n}}\text{(ζ) F(ζ) dζ}$, where F denotes the Laplace transform of f, Γ ? Ω is a simple closed contour chosen so that F is analytic outside and on Ω, and g_n is analytic on Ω. The specific functionals considered by this paper are patterned after the Lidstone functions, L_2n(f) = f⁽²ⁿ⁾(0) and L_{2n + 1}(f) = f⁽²ⁿ⁾(1), in that their sequence of generating functions {g_n} are “periodic.” Set g_{pn + k}(ζ) = h_k(ζ) ζ^pn, where p is a positive integer and each h_k (k = 0, 1,…, p ? 1) is analytic on Ω. We find necessary and sufficient conditions for $\text{f ∈ k[Ω]}\text{with}\text{L}{}_{\mathrm{n}}\text{(f) = 0 (n = 0, 1,…)}$. DeMar previously was able to find necessary conditions [7]. Next, we generalize {L_n} in several ways and find corresponding necessary and sufficient conditions.     

A method of feasible directions using function approximations,with applications to min max problems

This paper presents a demonstrably convergent method of feasible directions for solving the problem min{φ(ξ)| gⁱ(ξ)?0i=1,2,…,m}, which approximates, adaptively, both φ(x) and ▽φ(x). These approximations are necessitated by the fact that in certain problems, such as when $\text{φ(x) =}\text{max}\text{{f(x, y) ¦ y ? Ω}{}_{\mathrm{y}}\text{}}$, a precise evaluation of φ(x) and ▽φ(x) is extremely costly. The adaptive procedure progressively refines the precision of the approximations as an optimum is approached and as a result should be much more efficient than fixed precision algorithms.It is outlined how this new algorithm can be used for solving problems of the form $\text{min}{}_{\mathrm{y}}\text{? Ω}{}_{\mathrm{x}}\text{max}{}_{\mathrm{y}}\text{? Ω}{}_{\mathrm{y}}\text{f(x, y)}$ under the assumption that Ωm_ξ={x|gⁱ(x)?0, j=1,…,s} ∩$\text{R}$ⁿ, Ω_y={y|ζ_i(y)?0, i-1,…,t} ∩ $\text{R}$^m, with f, g^j, ζⁱ continuously differentiable, f(x, ·) concave, ζⁱ convex for $\text{i = 1,…, t,}\text{and}\text{Ω}{}_{\mathrm{x}}\text{, Ω}{}_{\mathrm{y}}$ compact.     

Monotone-gradient systems

The paper studies the system $\text{z}\text{?}\text{+ ?(g}{}_1\text{(z)) = ?(g}{}_2\text{(z))}$, where ? is monotone and g₁ and g₂ are gradient functions. This structure is introduced in connection with a new problem of control of the phase portrait of the system. For the studied problem, necessary and sufficient conditions are obtained.     

Square roots of elliptic operators

Consider an elliptic sesquilinear form defined on $\text{V}$ × $\text{V}$ by $\text{J[u, v] = ∫}{}_{\mathrm{\Omega }}\text{a}{}_{\mathrm{jk}}\text{?u}\text{?x}{}_{\mathrm{k}}\text{}\text{?}\text{t6v}\text{?x}{}_{\mathrm{j}}\text{+ a}{}_{\mathrm{k}}\text{?u}\text{?x}{}_{\mathrm{k}}\text{v}\text{?}\text{+ α}{}_{\mathrm{j}}\text{u}\text{}\text{?}\text{t6v}\text{?x}{}_{\mathrm{j}}\text{+ au}\text{v}\text{?}\text{dx}$, where $\text{V}$ is a closed subspace of $\text{H}{}^1\text{(Ω)}$ which contains $\text{C}{}_0{}^{\mathrm{\infty }}\text{(Ω)}$, Ω is a bounded Lipschitz domain in $\text{R}$ⁿ, $\text{a}{}_{\mathrm{jk}}\text{, a}{}_{\mathrm{k}}\text{, α}{}_{\mathrm{j}}\text{, a ? L}{}_{\mathrm{\infty }}\text{(Ω),}\text{and Re}\text{a}{}_{\mathrm{jk}}\text{ζ}{}_{\mathrm{k}}\text{ζ}{}_{\mathrm{j}}\text{? κ > 0}$ for all ζ?$\text{C}$ⁿ with ¦ζ¦ = 1. Let L be the operator with largest domain satisfying J[u, v] = (Lu, v) for all υ∈$\text{V}$. Then L + λI is a maximal accretive operator in $\text{L}{}_2\text{(Ω)}$ for λ a sufficiently large real number. It is proved that $\text{(L + λI)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ is a bounded operator from $\text{V}$ to $\text{L}{}_2\text{(Ω)}$ provided mild regularity of the coefficients is assumed. In addition it is shown that if the coefficients depend differentiably on a parameter t in an appropriate sense, then the corresponding square root operators also depend differentiably on t. The latter result is new even when the forms J are hermitian.     

Unitary interpolants,factorization indices and infinite Hankel block matrices

The existence, uniqueness, and construction of unitary n × n matrix valued functions $\text{?(ζ) = ∑}{}_{\mathrm{j\; =\; ?\infty }}{}^{\mathrm{\infty }}\text{?}{}_{\mathrm{j}}\text{ζ}{}^{\mathrm{j}}$ in Wiener-like algebras on the circle with prescribed matrix Fourier coefficients $\text{?}{}_{\mathrm{j}}\text{= γ}{}_{\mathrm{j}}$ for j ? 0 are studied. In particular, if $\text{Σ ¦γ}{}_{\mathrm{j}}\text{¦ < ∞}$, then such an ? exists with $\text{Σ ¦?}{}_{\mathrm{j}}\text{¦ < ∞}$ if and only if ∥Γ₀∥ ? 1, where Γ_v, denotes the infinite block Hankel matrix (γ_{j + k + v}), j, k = 0, 1,…, acting in the sequence space l_n². One of the main results is that the nonnegative factorization indices of every such ? are uniquely determined by the given data in terms of the dimensions of the kernels of $\text{I ? Γ}{}_{\mathrm{v}}{}^1\text{Γ}{}_{\mathrm{v}}$, whereas the negative factorization indices are arbitrary. It is also shown that there is a unique such ? if and only if the data forces all the factorization indices to be nonnegative and simple conditions for that and a formula for ? in terms of certain Schmidt pairs of Γ₀ are given. The results depend upon a fine analysis of the structure of the kernels of $\text{I ? Γ}{}_{\mathrm{v}}{}^1\text{Γ}{}_{\mathrm{v}}$ and of the one step extension problem of Adamjan, Arov, and Krein (Funct. Anal. Appl.2 (1968), 1–18). Isometric interpolants for the nonsquare case are also considered.     

Harmonic analysis on unitary groups

A theory of harmonic analysis on a metric group (G, d) is developed with the model of U$\text{U}$, the unitary group of a C¹-algebra $\text{U}$, in mind. Essential in this development is the set $\text{G}\text{?}{}_{\mathrm{d}}$ of contractive, irreducible representations of G, and its concomitant set P_d(G) of positive-definite functions. It is shown that $\text{G}\text{?}{}_{\mathrm{d}}$ is compact and closed in $\text{G}\text{?}$. The set $\text{G}\text{?}{}_{\mathrm{d}}$ is determined in a number of cases, in particular when G = U($\text{U}$) with $\text{U}$ abelian. If $\text{U}$ is an AW¹-algebra, it is shown that $\text{G}\text{?}$_d is essentially the same as $\text{U}\text{?}$. Unitary groups are characterised in terms of a certain Lie algebra $\text{g}$_u and several characterisations of G = U($\text{U}$) when $\text{U}$ is abelian are given.     

Connected matroids with the smallest whitney numbers

In “The Slimmest Geometric Lattices” (Trans. Amer. Math. Soc.). Dowling and Wilson showed that if G is a combinatorial geometry of rank r(G) = n, and if _X(G) = Σμ(0, x)λ^{r ? r(x)} = Σ (?1)^{r ? k}W_kλ^k is the characteristic polynomial of G, then

$\text{w}{}_{\mathrm{k}}\text{?}\text{r}\text{k}\text{+n}\text{r?1}\text{k}$

Thus γ(G) ? 2^{r ? 1} (n+2), where γ(G) = Σw_k. In this paper we sharpen these lower bounds for connected geometries: If G is connected, r(G) ? 3, and n(G) ? 2 ((r, n) ≠ (4,3)), then

$\text{w}{}_{\mathrm{i}}\text{?}\text{r}\text{i}\text{+ n}\text{r}\text{i+1}\text{for i>1; w}{}_1\text{?r+n}\text{r}\text{2}\text{? 1;}$

|μ| ? (r? 1)n; and γ ? (2^{r ? 1} ? 1)(2n + 2). These bounds are all achieved for the parallel connection of an r-point circuit and an (n + 1)point line. If G is any series-parallel network, $\text{r(G) = r(}\text{G}\text{?}\text{) = 4}$, and $\text{n(G) = n(}\text{G}\text{?}\text{) = 3}$ then $\text{(w}{}_1\text{(G))}{}^4{}_{\mathrm{t-G}}\text{? (w}{}_1\text{(}\text{G}\text{?}\text{)) = (8, 20, 18, 7, 1)}$. Further, if β is the Crapo invariant,

$\text{β(G)=}\text{d}{}_{\mathrm{X}}\text{(G)}\text{dλ}\text{(1)}\text{,}$

then β(G) ? max(1, n ? r + 2). This lower bound is achieved by the parallel connection of a line and a maximal size series-parallel network.     

La “conjecture des cylindres”

The “cylinder conjecture” is to suppose that, if K is a gauge, the critical constants of C(K) = K ×] ? 1, +1 [? Rⁿ⁺¹ and of its basis K ? Rⁿ are equal. The connection with packing constants is studied. The concept of Za(ssenhaus)-packing is introduced. ⊕_i=1^hG + (i ? 1)a (G a lattice) is a linear h-lattice, $\text{ζ}{}_{\mathrm{h}}\text{′(K),}\text{ζ}\text{′}{}_{\mathrm{h}}\text{(K)}$, $\text{η}{}_{\mathrm{h}}\text{′(K),}\text{η}\text{′}{}_{\mathrm{h}}\text{(K)}$ the maximum density for translates of K by a linear h-lattice if the translates form a Za-packing for ζ, a packing for η, and if this packing is strict for ^. For K a bounded central star body, it is possible to find H with ζ₁(C(K)) ≤ 2 ζ_H′(K). H is precised for K a gauge and for K = Bⁿ. It is proved by Woods' methods that $\text{η}{}_1\text{(C(B}{}^4\text{)) =}\text{sup}{}_{\mathrm{i=1,\; 3,\; 4,\; 6,}}\text{7}\text{η}{}_{\mathrm{i}}\text{(B}{}^4\text{)}$; a result of Cleaver is used.     

A rapidly convergent iteration method and Gâteaux differentiable operators

Let {F_r}_0?r?p be a family of Banach spaces satisfying, if 0?r₁?r₂?p, (i)F_r1 ? F_r2; (ii)$\text{¦f¦}{}_{\mathrm{r1}}\text{? ¦f¦}{}_{\mathrm{r2}}\text{(f ? F}{}_{\mathrm{r1}}\text{)}$; and (iii)$\text{?(r) = ln(¦f¦}{}_{\mathrm{r}}\text{)}$ is a convex function. Let G₀ be a Banach space and. $\text{F}$ be a Gâteaux differentiate mapping, and suppose that $\text{F}$′(x)(F_p) is dense in G₀. Under appropriate assumptions, the equation $\text{F}$(x)=0 has a solution in F_r for 0?r?p. The results extend the Inverse Function Theorem of J. Moser to the class of Gâteaux differentiable operators.     

A multiplication of distributions

If Ω denotes an open subset of $\text{R}$ⁿ (n = 1, 2,…), we define an algebra $\text{g}$ (Ω) which contains the space $\text{D}$′(Ω) of all distributions on Ω and such that $\text{C}{}^{\mathrm{\infty }}\text{(Ω)}$ is a subalgebra of $\text{G}$ (Ω). The elements of $\text{G}$ (Ω) may be considered as “generalized functions” on Ω and they admit partial derivatives at any order that generalize exactly the derivation of distributions. The multiplication in $\text{G}$(Ω) gives therefore a natural meaning to any product of distributions, and we explain how these results agree with remarks of Schwartz on difficulties concerning a multiplication of distributions. More generally if q = 1, 2,…, and $\text{?∈O}{}_{\mathrm{M}}\text{(}\text{R}{}^{\mathrm{2q}}\text{)}$—a classical Schwartz notation—for any G₁,…,G_q∈G(σ), we define naturally an element $\text{?G}{}_1\text{,…,G}{}_{\mathrm{q}}\text{∈G(σ)}$. These results are applied to some differential equations and extended to the vector valued case, which allows the multiplication of vector valued distributions of physics.     

Test solutions of porous media problems

Laminar isothermal fluid flow of two immiscible compressible fluid phases in a porous medium is formulated in terms of four unknown functions ?₁, ?₂, S₁ and S₂ in a pair of partial differential equations, $\text{(}\text{?}\text{?t}\text{)[φ(x, t)S}{}_{\mathrm{i}}\text{?}{}_{\mathrm{i}}\text{] = (}\text{?}\text{?x}\text{){κ(x, t) σ}{}_{\mathrm{i}}\text{(S}{}_{\mathrm{i}}\text{)(}\text{?}\text{?x}\text{)[Φ}{}_{\mathrm{i}}\text{(?}{}_{\mathrm{i}}\text{)]}}$, and a pair of auxiliary relations, S₁ = Γ₁(?₁, ?₂) and S₂ = 1 ? S₁. This system is studied in terms of solutions which are constant along curves, viz., horizontal lines, vertical lines, and parabolas relevant to the parabolic nature of each of the partial differential equations in the system. Such solutions are described, although subject to solution of ordinary differential equations, for use in testing either numerical methods or proposed theorems for the original larger problem.     

On the control of certain interacting populations

We study the time optimal control of the system $\text{x}\text{?}{}_1\text{= x}{}_1\text{?}{}_1\text{(x}{}_1\text{, x}{}_2\text{) + u}{}_1\text{(t) g}{}_1\text{(x}{}_1\text{),}\text{x}\text{?}{}_2\text{= x}{}_2\text{?}{}_2\text{(x}{}_1\text{, x}{}_2\text{) + u}{}_2\text{(t)g}{}_2\text{(x}{}_2\text{)}$, where x₁ is the size of the population of one species, x₂ is the population size of the second species, ?₁ and ?₂ are the fractional growth rates of the respective species, g₁ and g₂ are nowhere vanishing functions of class C¹(0, + ∞), and the control u(t) = (u₁(t), u₂(t)) takes on values in a closed rectangle. The functions ?₁ and ?₂ are chosen to represent prey-predator, competitive, and symbiotic interactions.We show, for the various interactions, that a time optimal control, if it exists, must be “bang-bang,” and give sufficient conditions for the controllability, and for the existence, of time optimal controls of the above system.     

Polynomials which take Gaussian integer values at Gaussian integers

A factorial set for the Gaussian integers is a set G = {g₁, g₂ … g_n} of Gaussian integers such that $\text{G(z) =}\text{Π}{}_{\mathrm{k}}\text{(z ? g}{}_{\mathrm{k}}\text{)}\text{g}{}_{\mathrm{k}}$ takes Gaussian integer values at Gaussian integers. We characterize factorial sets and give a lower bound for $\text{max}{}_{\mathrm{<mtext>\parallel z\parallel 2=</mtext><mtext>n</mtext><mtext>\pi </mtext>}}\text{∥ G(z)∥}$. It is conjectured that there are infinitely many factorial sets. A Gaussian integer valued polynomial (GIP) is a polynomial with the title property. A bound similar to the above is given for max_∥z∥2=n ∥ G(z)∥ if G(z) is a GIP. There is a relation between factorial sets and testing for GIP's. We discuss this and close with some examples of factorial sets, and speculate on how to find more.     

A complete set of invariants for finite groups and other results

For a finite group G and a set I ? {1, 2,…, n} let

${}_{\mathrm{G}}\text{(n,I) = ∑}{}_{\mathrm{g\; \in \; G}}\text{ε}{}_1\text{(g)?ε}{}_2\text{(g)???ε}{}_{\mathrm{n}}\text{(g)}$

,where

$\text{ε}{}_{\mathrm{i}}\text{(g)=g}\text{if}\text{i=∈ I,}$

$\text{ε}{}_{\mathrm{l}}\text{(g)=l}\text{if}\text{i=∈ I.}$

We prove, among other results, that the positive integers

$\text{tr}\text{(e}{}_{\mathrm{G}}\text{(n,I}{}_1\text{)+?+e}{}_{\mathrm{G}}\text{(n,I}{}_{\mathrm{r}}\text{))}{}^{\mathrm{k}}\text{:n,r,k,?1, I}{}_{\mathrm{j}}\text{?{1,…,n}, 1?|i}{}_{\mathrm{j}}\text{|?3}$

for 1 ? j ? r, I_j1 ∩ I_j2 ∩ I_j3 ∩ I_j4 = Ø for any 1 ? j₁ <j₂ <j₃ <j₄ ? r, determine G up to isomorphism. We also show that under certain assumptions finite groups are determined up to isomorphism by the number of their subgroups.