Packing a convex domain with similar convex domains

Given a convex domain C and a positive integer k, inscribe k nonoverlapping convex domains into C, all of them similar to C. Denote by f(k) the maximal sum of their circumferences. In this paper it is shown, that for C square, parallelogram or triangle (1) the first increase of f(k) after k = l² occurs not later than at k = l² + 2, (2) constructions can be given, where the following lower bounds are attained for f(k) = f(l² + j):

$\text{(}\text{1}\text{c}\text{) ? l +}\text{(j ? 1)}\text{2l}\text{j}\text{odd}\text{, l? 2}$

$\text{? l +}\text{j}\text{2}\text{(l + 1) j}\text{even}\text{, l?2}$

where c denotes the circumference of C.     

A note on the least prime in an arithmetic progression

Let k, l denote positive integers with (k, l) = 1. Denote by p(k, l) the least prime p ≡ l(mod k). Let P(k) be the maximum value of p(k, l) for all l. We show $\text{lim inf}\text{P(k)}\text{(?(k)}\text{log}\text{k)}\text{≥ e}{}^{\mathrm{\gamma }}\text{= 1.78107…}$, where γ is Euler's constant and ? is Euler's function. We also show $\text{P(k)}\text{(?(k)}\text{log}\text{k)}\text{→ ∞}$ for almost all k.     

On a problem of C. C. Chen and D. E. Daykin

Let α(k, p, h) be the maximum number of vertices a complete edge-colored graph may have with no color appearing more than k times at any vertex and not containing a complete subgraph on p vertices with no color appearing more than h times at any vertex. We prove that $\text{α(k, p, h) ≤ h + 1 + (k ? 1){(p ? h ? 1) × (h}{}^{\mathrm{p}}\text{+ 1)}}{}^{\mathrm{<mtext>1</mtext><mtext>h</mtext>}}$ and obtain a stronger upper bound for α(k, 3, 1). Further, we prove that a complete edge-colored graph with n vertices contains a complete subgraph on p vertices in which no two edges have the same color if

$\text{(}\text{n}\text{3}\text{)>(}\text{p}\text{3}\text{)}\text{Σ}\text{i=1}\text{t}\text{(}\text{e}{}_{\mathrm{i}}\text{2}\text{)}$

where e_i is the number of edges of color i, 1 ≤ i ≤ t.     

Nowhere zero flow and circuit covering in regular matroids

Let s(k) be the smallest s such that if there exists a k-nowhere zero flow in a regular matroid M, then M can be covered by circuits, the total length of which is at most s|M|. A recursive formula for the evaluation of s(k) is given: $\text{s(kt) ≤}\text{(s(k)(kt ? t) + s(t)(kt ? k))}\text{(kt ? 1)}$. By means of this formula s(k) is found for k = 2, 3, 4, 6, 7, 8. “Natural” proofs for graph theoretical results are obtained.     

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)}$

     

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.     

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.     

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).     

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.     

Finding the maximum,merging, and sorting in a parallel computation model

A model for synchronized parallel computation is described in which all p processors have access to a common memory. This model is used to solve the problems of finding the maximum, merging, and sorting by p processors. The main results are: 1. Finding the maximum of n elements (1 < p ≤ n) within a depth of $\text{O(}\text{n}\text{p}\text{+}\text{log log}\text{p)}$; (optimal for $\text{p ≤}\text{n}\text{log log}\text{n}$). 2. Merging two sorted lists of length m and n (m ≤ n) within a depth of $\text{O(}\text{n}\text{p}\text{+}\text{log}\text{n)}$ for p ≤ n (optimal for $\text{p ≤}\text{n}\text{log}\text{n}$), $\text{O(}\text{log}\text{m}\text{log}\text{p}\text{n}\text{)}$ for $\text{p ≥ n(= O(k)}\text{if}\text{p = m}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}\text{n, k > 1)}$. 3. Sorting n elements within a depth of $\text{O(}\text{n}\text{p}\text{log}\text{n}\text{+}\text{log}\text{n}\text{log}\text{p)}$ for p ≤ n, (optimal for $\text{p ≤}\text{n}\text{log}\text{n}$). $\text{O(}\text{log}{}^2\text{n}\text{log}\text{p}\text{n}\text{) +}\text{log}\text{n)}$ for $\text{p ≥ n (= O(k}\text{log}\text{n)}\text{if}\text{p = n}{}^{\mathrm{<mtext>1+</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{, k > 1)}$. The depth of O(klogn) for $\text{p = n}{}^{\mathrm{<mtext>1+</mtext><mtext>1</mtext><mtext>k</mtext>}}$ processors was also achieved by Hirschberg (Comm. ACM21, No. 8 1978, 657–661) and Preparata IEEE Trans ComputersC-27 (July 1978), 669–673). Our algorithm is substantially simpler. All the elementary operations including allocation of processors to their jobs are taken into account in deriving the depth complexity and not only comparisons.     

On the length of optimal TSP circuits in sets of bounded diameter

Let V be a set of n points in R^k. Let d(V) denote the diameter of V, and l(V) denote the length of the shortest circuit which passes through all the points of V. (Such a circuit is an “optimal TSP circuit”.) l^k(n) are the extremal values of l(V) defined by l^k(n)=max{l(V)|V∈V_n^k}, where V_n^k={V|V?R^k,|V|=n, d(V)=1}. A set V∈V_n^k is “longest” if l(V)=l^k(n). In this paper, first some geometrical properties of longest sets in R² are studied which are used to obtain l²(n) for small n′s, and then asymptotic bounds on l^k(n) are derived. Let δ(V) denote the minimal distance between a pair of points in V, and let: δ^k(n)=max{δ(V)|V∈V_n^k}. It is easily observed that $\text{δ}{}^{\mathrm{k}}\text{(n)=O(n}{}^{\mathrm{<mtext>?1</mtext><mtext>k</mtext>}}\text{)}$. Hence, $\text{c}{}_{\mathrm{k}}\text{=}\text{lim sup}{}_{\mathrm{n\to \infty }}\text{δ}{}^{\mathrm{k}}\text{(n)n}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}$ exists. It is shown that for all $\text{n, c}{}_{\mathrm{k}}\text{n}{}^{\mathrm{<mtext>?1</mtext><mtext>k</mtext>}}\text{≤δ}{}^{\mathrm{k}}\text{(n)}$, and hence, for all $\text{n, l}{}^{\mathrm{k}}\text{(n)≥ c}{}_{\mathrm{k}}\text{n}{}^{\mathrm{<mtext>1?1</mtext><mtext>k</mtext>}}$. For k=2, this implies that $\text{l}{}^2\text{(n)≥(}\text{π}{}^2\text{12}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>4</mtext>}}\text{n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, which generalizes an observation of Fejes-Toth that $\text{lim}{}_{\mathrm{n\to \infty }}\text{l}{}^2\text{(n)n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{≥(}\text{π}{}^2\text{12}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>4</mtext>}}$. It is also shown that $\text{l}{}^{\mathrm{k}}\text{(n) ≤ [}\text{(3?√3)k}\text{(k?1)}\text{]nδ}{}^{\mathrm{k}}\text{(n) + o(n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{) ≤ [}\text{(3?√3)k}\text{(k?1)}\text{]n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{+ o(n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{)}$. The above upper bound is used to improve related results on longest sets in k-dimensional unit cubes obtained by Few (Mathematika2 (1955), 141–144) for almost all k′s. For k=2, Few's technique is used to show that $\text{l}{}^2\text{(n)≤(}\text{πn}\text{2}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{+ O(1)}$.     

Pancyclic graphs and a conjecture of Bondy and Chvátal

A p-vertex graph is called pancyclic if it contains cycles of every length l, 3 ≤ l ≤ p. In this paper we prove the following conjecture of Bondy and Chvátal: If a graph G has vertex degree sequence d₁ ≤ d₂ ≤ … ≤ d_ν, and if $\text{d}{}_{\mathrm{k}}\text{≤ k <}\text{p}\text{2}$ implies d_ν?k ≥ p ? k, then G is pancyclic or bipartite.     

An existence theorem for antichains

Let k₁, k₂,…, k_n be given integers, 1 ? k₁ ? k₂ ? … ? k_n, and let S be the set of vectors x = (x₁,…, x_n) with integral coefficients satisfying 0 ? x_i ? k_i, i = 1, 2, 3,…, n. A subset H of S is an antichain (or Sperner family or clutter) if and only if for each pair of distinct vectors x and y in H the inequalities x_i ? y_i, i = 1, 2,…, n, do not all hold. Let |H| denote the number of vectors in H, let K = k₁ + k₂ + … + k_n and for 0 ? l ? K let (l)H denote the subset of H consisting of vectors h = (h₁, h₂,…, h_n) which satisfy h₁ + h₂ + … + h_n = l. In this paper we show that if H is an antichain in S, then there exists an antichain H′ in S for which |(l)H′| = 0 if $\text{l <}\text{K}\text{2}$, $\text{|(}\text{K}\text{2}\text{)H′| = |(}\text{K}\text{2}\text{)H|}$ if K is even and |(l)H′| = |(l)H| + |(K ? l)H| if $\text{l>}\text{K}\text{2}$.     

Pairs of additive equations II. Large odd degree

Let k be an odd positive integer. Davenport and Lewis have shown that the equations

$\text{a}{}_1\text{x}{}_1{}^{\mathrm{k}}\text{+…+a}{}_{\mathrm{n}}\text{x}{}_{\mathrm{n}}{}^{\mathrm{k}}\text{=0}$

with integer coefficients, have a nontrivial solution in integers x₁,…, x_N provided that

$\text{N?[36klog6k]}$

Here it is shown that for any ? > 0 and k > k₀(?) the equations have a nontrivial solution provided that

$\text{N?}\text{8}\text{log 2}\text{+?}\text{k log k.}$

     

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.     

Polynomials generalizing binomial coefficients and their application to the study of Fermat's last theorem

We study properties of the polynomials φ_k(X) which appear in the formal development Π_{k ? 0}ⁿ (a + bX^k)^rk = Σ_{k ≥ 0}φ_k(X) a^{r ? k}b^k, where r_k ∈ $\text{l}$ and r = Σr_k. this permits us to obtain the coefficients of all cyclotomic polynomials. Then we use these properties to expand the cyclotomic numbers G_r(ξ) = Π_{k = 1}^{p ? 1} (a + bξ^k)^kr, where p is a prime, ξ is a primitive pth root of 1, a, b ∈ $\text{l}$ and 1 ≤ r ≤ p ? 3, modulo powers of ξ ? 1 (until (ξ ? 1)^{2(p ? 1) ? r}). This gives more information than the usual logarithmic derivative. Suppose that $\text{p ? ab(a + b)}$. Let $\text{m = ?}\text{b}\text{a}$. We prove that G_r(ξ) ≡ c^p mod p(ξ ? 1)² for some c ∈ $\text{l}$, if and only if Σ_{k = 1}^{p ? 1}k^{p ? 2 ? r}m^k ≡ 0 (mod p). We hope to show in this work that this result is useful in the study of the first case of Fermat's last theorem.     

A problem of Zarankiewicz

Zarankiewicz, in problem P 101, Colloq. Math., 2 (1951), p. 301, and others have posed the following problem: Determine the least positive integer k_α,β(m, n) so that if a 0,1-matrix of size m by n contains k_α,β(m, n) ones then it must have an α by β submatrix consisting entirely of ones. This paper improves upon previously known upper bounds for k_α,β(m, n) by proving that $\text{k}{}_{\mathrm{\alpha \beta }}\text{(m,n)?}\text{1+((β?1)}\text{(}\text{p}\text{α?1}\text{))(}\text{m}\text{α}\text{)}\text{+}\text{((p+1)(α?1)}\text{α}\text{)n}$ for each integer p greater than or equal to α ? 1. Each of these inequalities is better than the others for a specific range of values of n. Equality is shown to hold infinitely often for each value of p. Finally some applications of this result are made to arrangements of lines in the projective plane.     

Approximate solutions of functional differential equations

The author discusses the best approximate solution of the functional differential equation x′(t) = F(t, x(t), x(h(t))), 0 < t < l satisfying the initial condition x(0) = x₀, where x(t) is an n-dimensional real vector. He shows that, under certain conditions, the above initial value problem has a unique solution y(t) and a unique best approximate solution $\text{p}\text{?}{}_{\mathrm{k}}\text{(t)}$ of degree k (cf. [1]) for a given positive integer k. Furthermore, $\text{sup}{}_{\mathrm{0?t?l}}\text{¦}\text{p}\text{?}{}_{\mathrm{k}}\text{(t) ? y(t)¦ → 0}\text{as}\text{k → ∞}$, where ¦ · ¦ is any norm in Rⁿ.     

On the order of the error function of the (k,r)-integers

Let k and r be fixed integers such that 1 < r < k. Any positive integer n of the form n = a^kb, where b is r-free, is called a (k, r)-integer. In this paper we prove that if Q_k,r(x) denotes the number of (k, r)-integers ≤ x, then $\text{Q}{}_{\mathrm{k,r}}\text{(x) =}\text{xζ(k)}\text{ζ(r)}\text{+ Δ}{}_{\mathrm{k,r}}\text{(x)}$, where $\text{Δ}{}_{\mathrm{k,r}}\text{(x) = O(x}{}^{\mathrm{<mtext>1</mtext><mtext>r</mtext>}}\text{exp}\text{[?B}\text{log}{}^{\mathrm{<mtext>3</mtext><mtext>5</mtext>}}\text{x (}\text{log log}\text{x)}{}^{\mathrm{<mtext>?</mtext><mtext>1</mtext><mtext>5</mtext>}}\text{])}$, B being a positive constant depending on r and the O-estimate is uniform in k. On the assumption of the Riemann hypothesis, we improve the above order estimate of Δ_k,r(x) and prove that

$\text{1}\text{x}\text{∫}\text{1}\text{α}\text{δ}{}_{\mathrm{k,r}}\text{(t)dt=0(x}\text{1}\text{k}\text{ω(x))}\text{or}\text{0(x}{}^{\mathrm{3/(4r+1)}}\text{ω(x))}$

, according as $\text{k ≤}\text{(4r + 1)}\text{3}$ or $\text{k >}\text{(4r + 1)}\text{3}$, where ω(x) = exp [B log x(log log x)^?1].