A generalization of the Kruskal-Katona theorem

Let k_n ? k_n?1 ? … ? k₁ be positive integers and let ($\text{i}\text{j}$) denote the coefficient of xⁱ in $\text{Π}\text{r=1}\text{j}\text{(1 + x + x}{}^2\text{+ … + x}{}^{\mathrm{kr}}\text{)}$. For given integers l, m, where 1 ? l ? k_n + k_n?1 + … + k₁ and $\text{1 ? m ? (}\text{n}\text{n}\text{)}$, it is shown that there exist unique integers m(l), m(l ? 1),…, m(t), satisfying certain conditions, for which $\text{m = (}\text{m(l)}\text{l}\text{+ (}\text{m(l?1)}\text{l?1}\text{) + … + (}\text{m(t)}\text{t}\text{)}$. Moreover, any m l-subsets of a multiset with k_i elements of type i, i = 1, 2,…, n, will contain at least $\text{(}\text{m(l)}\text{l?1}\text{) + (}\text{m(l?1)}\text{l?2}\text{) + … + (}\text{m(t)}\text{t?1}$ different (l ? 1)-subsets. This result has been anticipated by Greene and Kleitman, but the formulation there is not completely correct. If k₁ = 1, the numbers ($\text{j}\text{i}$) are binomial coefficients and the result is the Kruskal-Katona theorem.     

Principle of inclusion-exclusion on semilattices

We introduce an enumeration theorem under lattice action. Let L be a finite semilattice and Ω be a nonempty set. Let $\text{f: L → P(Ω)}$ be a map satisfying f(x ? y) ? f(x) ∩ f(y), where ? and $\text{P}$(Ω) mean “join” and the power set of Ω, respectively. Then

$\text{m}\text{∪}\text{x?L}\text{?(x)}\text{=}\text{Σ}\text{c?C}\text{(?1)}{}^{\mathrm{l(c)}}\text{m}\text{∩}\text{x?c}\text{?(x)}$

, where C is the set of all chains in L and l(c) denotes the length of a chain c. Also the theorem can be dualized. Furthermore, we describe two applications of the theorem to a Boolean lattice of sets and a partition lattice of a set.     

Quantization of the action of U(k,l) on R2(K + l)

The natural action of U(k, l) on $\text{C}$^{k + l} leaves invariant a real skew non-degenerate bilinear form B, which turns $\text{C}$^{k + l} into a symplectic manifold (M, ω). The polarization F of M defined by the complex structure of $\text{C}$^{k + l} is non-positive. If L is the prequantization complex line bundle carried by (M, ω), then U(k, l) acts on the space $\text{U}$ of square-integrable $\text{L ? ΛF}{}^1$ forms on M, leaving invariant the natural non-degenerate, but non-definite, inner product ((·, ·)) on $\text{U}$. The polarization F also defines a closed, densely defined covariant differential ?? on $\text{U}$ which is U(k, l)-invariant. Let $\text{⊥}$ denote orthocomplementation with respect to ((·, ·)). It is shown that the restriction of ((·, ·)) to the U(k, l)-stable subspace ? (Ker ??) ∩ (Im ??)^$\text{⊥}$ is semi-definite and that the unitary representation of Uk, l on the Hilbert space $\text{H}$ arising from ? by dividing out null vectors is unitarily equivalent to the representation of U(k, l) obtained from the tensor product of the metap ectic and $\text{Det}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}$ representations of MU(k, l), the double cover of U(k, l).     

Product formulas for semigroups with elliptic generators

Real constant coefficient nth order elliptic operators, Q, which generate strongly continuous semigroups on L²($\text{R}$^k) are analyzed in terms of the elementary generator,

$\text{A = (?n)}{}^{\mathrm{<mtext>(</mtext><mtext>n</mtext><mtext>2</mtext><mtext>\; ?\; 1</mtext>}}\text{)(n!)}{}^{\mathrm{?1}}\text{∑}\text{k}\text{j = 1}\text{?}{}^{\mathrm{n}}\text{?x}{}_{\mathrm{j}}{}^{\mathrm{n}}$

, for n even. Integral operators are defined using the fundamental solutions p_n(x, t) to u_t = Au and using real polynomials q_l,…, q_k on $\text{R}$^m by the formula, for q = (q_l,…, q_k),

$\text{(F(t)?)(x) = ∫}$

_$\text{R}$m

$\text{?(x + q(z)) P}{}_{\mathrm{n}}\text{(z, t)dz}$

. It is determined when, strongly on L²($\text{R}$^k),

$\text{e}{}^{\mathrm{tQ}}\text{=}\text{lim}\text{j → ∞}\text{F}\text{t}\text{j}{}^{\mathrm{j}}$

. If n = 2 or k = 1, this can always be done. Otherwise the symbol of Q must have a special form.     

Hecke operators and an identity for the dedekind sums

If h, k ∈ Z, k > 0, the Dedekind sum is given by

$\text{s(h,k) =}\text{∑}\text{μ=1}\text{k}\text{μ}\text{k}\text{hμ}\text{k}$

, with

$\text{((x)) = x ? [x] ?}\text{1}\text{2}\text{, x?Z}$

,

$\text{=0 , x∈Z}$

. The Hecke operators T_n for the full modular group SL(2, Z) are applied to log η(τ) to derive the identities (n ∈ Z⁺)

$\text{∑ ∑ s(ah+bk,dk) = σ(n)s(h,k)}$

,

$\text{ad=n b(}\text{mod}\text{d)}$

$\text{d>0}$

where (h, k) = 1, k > 0 and σ(n) is the sum of the positive divisors of n. Petersson had earlier proved (1) under the additional assumption k ≡ 0, h ≡ 1 (mod n). Dedekind himself proved (1) when n is prime.     

Merten's theorem for arithmetic progressions

Let k be an integer ≥ 1 and let l be an integer such that 1 ≤ l ≤ k, (l,k) = 1. An asymptotic formula (valid for large x) is obtained for the product

$\text{∏}\text{p≤x,p≡l(}\text{mod}\text{k)}\text{1?}\text{1}\text{p}$

, generalizing a familiar result of Mertens.     

Best quadrature formulas at equally spaced nodes

It has been known for some time that the trapezoidal rule $\text{T}{}_{\mathrm{n}}\text{f =}\text{1}\text{2}\text{f(0) + f(1) + … + f(n ? 1) +}\text{1}\text{2}\text{f(n)}$ is the best quadrature formula in the sense of Sard for the space W^1,p, all functions such that f′ ?L^p. In other words, the norm of the error functional Ef = ∝₀ⁿf(x) dx ? ∑_{k = 0}ⁿλ_kf(k) in W^1,p is uniquely minimized by the trapezoidal sum. This paper deals with quadrature formulas of the form ∑_{k = 0}ⁿ ∑_l?Jc_klf^(l)(k) where J is some subset of {0, 1,…, m ? 1}. For certain index sets J we identify the best quadrature formula for the space W^m,p, all functions such that f^(m)?L^p. As a result, we show that the Euler-Maclaurin quadrature formula

$\text{T}{}_{\mathrm{n}}\text{f +}\text{∑}\text{o<2v≤m}\text{B}{}_{\mathrm{2v}}\text{(2v)!}\text{(f (2v?1)(0) ? f (2v?1) (n))}$

is the best quadrature formula of the above form with J = {0, 1, 3,…, ?m ? 1} for the space W^m,p, providing m is an odd integer.     

Arithmetic properties of certain functions in several variables

If T is an n × n matrix with nonnegative integral entries, we define a transformation T: Cⁿ → Cⁿ by w = Tz where

$\text{W}{}_1\text{=}\text{∏}\text{j=1}\text{n}\text{z}{}_{\mathrm{j}}{}^{\mathrm{t}}\text{ij}\text{(1?i?n).}$

We consider functions f(z) of n complex variables which satisfy a functional equation giving f(Tz) as a rational function of ¹f(z) and we obtain conditions under which such a function f(z) takes transcendental values at algebraic points.     

On the number of combinations without unit separation

Let f(n, k) denote the number of ways of selecting k objects from n objects arrayed in a line with no two selected having unit separation (i.e., having exactly one object between them). Then, if $\text{n ? 2(k ? 1), f(n,k)=}\text{∑}\text{i=0}\text{κ}\text{(}\text{n?k+I?2i}\text{k?2i}\text{)}$ (where $\text{κ = [}\text{k}\text{2}\text{]}$). If n < 2(k ? 1), then f(n, k) = 0. In addition, f(n, k) satisfies the recurrence relation f(n, k) = f(n ? 1, k) + f(n ? 3, k ? 1) + f(n ? 4, k ? 2). If the objects are arrayed in a circle, and the corresponding number is denoted by g(n, k), then for n > 3, g(n, k) = f(n ? 2, k) + 2f(n ? 5, k ? 1) + 3f(n ? 6, k ? 2). In particular, if n ? 2k + 1 then $\text{(n,k)=(}\text{n?k}\text{k}\text{)+(}\text{n?k?1}\text{k?1}\text{)}$.     

An identity involving partitional generalized binomial coefficients

Define coefficients (_κ^λ) by C_λ(I_p + Z)/C_λ(I_p) = Σ_k=0^l Σ_{?∈$\text{P}$k} (_?^λ) C_κ(Z)/C_κ(I_p), where the C_λ's are zonal polynomials in p by p matrices. It is shown that C_?(Z) etr(Z)/k! = Σ_l=k^∞ Σ_{λ∈$\text{P}$l} (_?^λ) C_λ(Z)/l!. This identity is extended to analogous identities involving generalized Laguerre, Hermite, and other polynomials. Explicit expressions are given for all (_?^λ), ? ∈ $\text{P}$_k, k ≤ 3. Several identities involving the (_?^λ)'s are derived. These are used to derive explicit expressions for coefficients of $\text{C}{}_{\mathrm{\lambda }}\text{(Z)}\text{l}\text{!}$ in expansions of P(Z), $\text{etr}\text{(Z)}\text{k!}$ for all monomials P(Z) in s_j = tr Z^j of degree k ≤ 5.     

Construction of a recurrence relation for modified moments

In this paper we are constructing a recurrence relation of the form

$\text{∑}\text{i=0}\text{r}\text{ω}{}_{\mathrm{i}}\text{(k)m}{}_{\mathrm{k+i}}{}^{\mathrm{\{\lambda \}}}\text{[f] = ω(k)}$

for integrals (called modified moments)

$\text{m}{}_{\mathrm{k}}{}^{\mathrm{\{\lambda \}}}\text{[f]df=}\text{∫}\text{?1}\text{1}\text{f(x)C}{}_{\mathrm{k}}{}^{\mathrm{(\lambda )}}\text{(x)dx (k = 0,1,…)}$

in which C_k^(λ) is the k-th Gegenbauer polynomial of order $\text{λ(λ > ?}\text{1}\text{2}\text{)}$, and f is a function satisfying the differential equation

$\text{∑}\text{i=0}\text{n}\text{P}{}_{\mathrm{i}}\text{(x)f}{}^{\mathrm{(i)}}\text{(x) = p(x) (?1?x?1)}$

of order n, where p₀, p₁, …, p_n ? 0 are polynomials, and m_k^〈λ〉[p] is known for every k. We give three methods of construction of such a recurrence relation. The first of them (called Method I) is optimum in a certain sense.     

Note on lower bounds for the rank of a matrix

The following results are proved: Let A = (a_ij) be an n × n complex matrix, n ? 2, and let k be a fixed integer, 1 ? k ? n ? 1.(1) If there exists a monotonic G-function f = (f₁,…,f_n) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have

$\text{Π}\text{i∈S}\text{f}{}_{\mathrm{i}}\text{(A)<}\text{Π}\text{i∈S}\text{|a}{}_{\mathrm{ii}}\text{|,}$

then the rank of A is ? n ? k + 1. (2) If A is irreducible and if there exists a G-function f = (f₁,…,f_n) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have

$\text{Π}\text{i∈S}\text{f}{}_{\mathrm{i}}\text{(A)<}\text{Π}\text{i∈S}\text{|a}{}_{\mathrm{ii}}\text{|,}$

then the rank of A is ? n ? k + 1 if k ? 2, n ? 3; it is ? n ? 1 if k = 1.     

A note on the probabilistic approach to Turán's problem

The Turán number T(n, l, k) is the smallest possible number of edges in a k-graph on n vertices such that every l-set of vertices contains an edge. Given a k-graph H = (V(H), E(H)), we let X_s(S) equal the number of edges contained in S, for any s-set S?V(H). Turán's problem is equivalent to estimating the expectation E(X_l), given that min(X_l) ≥ 1. The following lower bound on the variance of X_s is proved:

$\text{Var(X}{}_{\mathrm{s}}\text{)?mm}\text{n?2k}\text{s?k}\text{n}\text{s}{}^{\mathrm{?1}}\text{n}\text{k}{}^1$

, where m = |E(H)| and $\text{m}\text{= (}{}_{\mathrm{k}}{}^{\mathrm{n}}\text{) ? m}$. This implies the following: putting t(k, l) = lim_n→∞T(n, l, k)(_kⁿ)^?1 then t(k, l) ≥ T(s, l, k)((_k^s) ? 1)^?1, whenever s ≥ l > k ≥ 2. A connection of these results with the existence of certain t-designs is mentioned.     

Omega theorems for the iterated additive convolution of a nonnegative arithmetic function

Let R_k(n) denote the number of ways of representing the integers not exceeding n as the sum of k members of a given sequence of nonnegative integers. Suppose that $\text{1}\text{2}\text{< β < k}$, $\text{δ =}\text{β}\text{2}\text{?}\text{β}\text{(4}\text{min}\text{(β,}\text{k}\text{2}\text{))}$ and

$\text{ξ=}\text{1/2β if β<k/2,}\text{β?1/2 if β=1/2,}\text{(k ? 2)(k + 1)/2k if k/2<β<k.}$

R. C. Vaughan has shown that the relation R_k(n) = G(n) + o(n^δ log^?ξn) as n → +∞ is impossible when G(n) is a linear combination of powers of n and the dominant term of G(n) is cn^β, c > 0. P. T. Bateman, for the case k = 2, has shown that similar results can be obtained when G(n) is a convex or concave function. In this paper, we combine the ideas of Vaughan and Bateman to extend the theorems stated above to functions whose fractional differences are of one sign for large n. Vaughan's theorem is included in ours, and in the case $\text{β <}\text{k}\text{2}$ we show that a better choice of parameter improves Vaughan's result by enabling us to drop the power of log n from the estimate of the error term.     

The enumeration of shift register sequences

A study is made of the number of cycles of length k which can be produced by a general n-stage feedback shift register. This problem is equivalent to finding the number of cycles of length k on the so-called de Bruijn-Good graph (Proc. K. Ned. Akad. Wet.49 (1946), 758–764; J. London Math. Soc.21 (3) (1946), 169–172). The number of cycles of length k in such a graph is denoted by β(n, k). From the-de Bruijn-Good graph, it can be shown that β(n, k) is also the number of cyclically distinct binary sequences of length k which have all k successive sets of n adjacent digits (called “n windows”) distinct (the sequence to be considered cyclically). After listing some known results for β(n, k), we show that

$\text{β(k?3, k)=β(k, k)?2φ}{}_{\mathrm{k,\; 2}}\text{+2}\text{for}\text{k?5}$

, where $\text{φ}{}_{\mathrm{k,\; r}}\text{?}$ the number of integers l ? k such that (k, l) ? r, and (k, l) denotes the greatest common divisor of k and l. From the results of several computer programs, it is conjectured that

$\text{β(k?4, k)=β(k, k)?4φ}{}_{\mathrm{k,\; 3}}\text{?2(k, 2)+10 (k?8)}$

,

$\text{β(k?5, k)=β(k, k)?8φ}{}_{\mathrm{k,\; 4}}\text{?(k, 3)+19 (k?11)}$

$\text{β(k?6, k)=β(k, k)?16φ}{}_{\mathrm{k,\; 5}}\text{?4(k, 2)?2(k, 3)+48 (k?15)}$

     

Generating functions for certain types of permutations

Generating functions are obtained for certain types of permutations analogous to up-down and down-up permutations. In each case the generating function is a quotient of entire functions; the denominator in each case is φ₀²(x) ? φ₁(x)φ₃(x), where

$\text{φ}{}_{\mathrm{j}}\text{(x)=}\text{∑}\text{n=o}\text{∞}\text{x}{}^{\mathrm{4n+j}}\text{(4n+j)}\text{!.}$

     

Partitions of large multipartites with congruence conditions. II

For 1 ≦ l ≦ j, let $\text{a}$_l = ?_h=1^q(l){a_lh + Mv: v = 0, 1, 2,…}, where j, M, q(l) and the a_lh are positive integers such that j > 1, a_l1 < … < a_lq(2) ≦ M, and let $\text{a}$_l^′ = $\text{a}$_l ∪ {0}. Let p(n : $\text{B}$) be the number of partitions of n = (n₁,…,n_j) where, for 1 ≦ l ≦ j, the lth component of each part belongs to $\text{B}$_l and let p¹(n : $\text{B}$) be the number of partitions of n into different parts where again the lth component of each part belongs to $\text{B}$_l. Asymptotic formulas are obtained for p(n : $\text{a}$), p¹(n : $\text{a}$) where all but one n_l tend to infinity much more rapidly than that n_l, and asymptotic formulas are also obtained for p(n : $\text{a}$′), p¹(n ; $\text{a}$′), where one n_l tends to infinity much more rapidly than every other n_l. These formulas contrast with those of a recent paper (Robertson and Spencer, Trans. Amer. Math. Soc., to appear) in which all the n_l tend to infinity at approximately the same rate.     

On constant discrete programming problems

Let H be a subset of the set S_n of all permutations

$\text{1}\text{2}\text{???}\text{n}\text{s(1)}\text{s(2)}\text{???}\text{s(n)}$

C=6c_ij6 a real n?n matrix L_c(s)=c_1s(1)+c_2s(2)+???+c_ns(n) for s ? H. A pair (H, C) is the existencee of reals a₁,b₁,a₂,b₂,…a_n,b_n, for which c_ij=a₁+b_j if (i,j)?D(H), where D(H)={(i,j):(?h?H)(j=h(i))}.For a pair (H,C) the specifity of it is proved in the case, when H is either a special cyclic class of permutations or a special union of cyclic classes. Specific pairs with minimal sets H are in some sense described.     

Über diej-ten Überdeckungsdichten konvexer Körper

Let for positive integersj,k,d and convex bodiesK of Euclideand-spaceE ^d of dimension at leastj V _{j, k} (K) denote the maximum of the intrinsic volumesV _j (C) of those convex bodies whosej-skeleton skel _j (C) can be covered withk translates ofK. Then thej-thk-covering density θ _j,k (K) is the ratiok V _j (K)/V _j,k (K). In particular, θ _d,k refers to the case of covering the entire convex bodiesC and the density is measured with respect to the volume while forj=d-1 the surface of the bodiesC is covered and accordingly the density is measured with respect to the surface area. The paper gives the estimate $$1 \leqslant \theta _{j,k} (K)< e (j + \sqrt {\pi /2} \sqrt {d - j} )< (d + 1) e$$ for thej-thk-covering density and some related results.     

An asymptotic relation for the zeros of Bessel functions

We define the function j_νκ for all real κ > 0 as follows: for κ = 1, 2, … the j_νκ denotes the kth positive zero of the Bessel function J_ν(z) of first kind and for k ? 1 < κ < k, j_νκ denotes the kth positive zero of the cylinder Bessel function C_ν(z) = cos αJ_ν(z) ? sin αY_ν(Z) with α = (k ? ν)π (see [2]), where Y_ν(x) is the Bessel function of second kind. We introduce the function ι(x) for x > ? 1,

$\text{l(x)=}\text{lim}\text{κ→∞}\text{j}{}_{\mathrm{\kappa ,x,\kappa }}\text{κ}$

. and we prove, among other things, the inequality $\text{j}{}_{\mathrm{\nu \kappa }}\text{< κι(}\text{ν}\text{κ}\text{)}$. Moreover, we find the first three terms of the asymptotic expansion of ι(x), for large values of x and other properties of this function.