On diophantine equations of the form {({\boldsymbol x}-{\boldsymbol a}_{\bf 1})({\boldsymbol x}-{\boldsymbol a}_{\bf 2}) \ldots ({\boldsymbol x}-{\boldsymbol a}_{\boldsymbol k}) + {\boldsymbol r} = {\boldsymbol y}^{ \boldsymbol n}}

Erd?s and Selfridge [3] proved that a product of consecutive integers can never be a perfect power. That is, the equation x(x?+?1)(x?+?2)...(x?+?(m???1))?=?y ⁿ has no solutions in positive integers x,m,n where m, n?>?1 and y?∈?Q. We consider the equation $$ (x-a_1)(x-a_2) \ldots (x-a_k) + r = y^n $$ where 0?≤?a ₁?<?a ₂?<???<?a _k are integers and, with r?∈?Q, n?≥?3 and we prove a finiteness theorem for the number of solutions x in Z, y in Q. Following that, we show that, more interestingly, for every nonzero integer n?>?2 and for any nonzero integer r which is not a perfect n-th power for which the equation admits solutions, k is bounded by an effective bound.     

The Erd?s-Ginzberg-Ziv theorem with units

Let x₁,…,x_r be a sequence of elements of Z_n, the integers modulo n. How large must r be to guarantee the existence of a subsequence x_i1,…,x_in and units α₁,…,α_n with α₁x_i1+?+α_nx_in=0? Our main aim in this paper is to show that r=n+a is large enough, where a is the sum of the exponents of primes in the prime factorisation of n. This result, which is best possible, could be viewed as a unit version of the Erd?s-Ginzberg-Ziv theorem. This proves a conjecture of Adhikari, Chen, Friedlander, Konyagin and Pappalardi.We also discuss a number of related questions, and make conjectures which would greatly extend a theorem of Gao.     

On a class of degenerate extremal graph problems

Given a class ? of (so called “forbidden”) graphs, ex (n, ?) denotes the maximum number of edges a graphG ⁿ of ordern can have without containing subgraphs from ?. If ? contains bipartite graphs, then ex (n, ?)=O(n ^2?c ) for somec>0, and the above problem is calleddegenerate. One important degenerate extremal problem is the case whenC _2k , a cycle of 2k vertices, is forbidden. According to a theorem of P. Erd?s, generalized by A. J. Bondy and M. Simonovits [3₂, ex (n, {C _2k })=O(n ^1+1/k ). In this paper we shall generalize this result and investigate some related questions.     

Collinear subsets of lattice point sequences—An analog of Szemerédi's theorem

Szemerédi's theorem states that given any positive number B and natural number k, there is a number n(k, B) such that if n ? n(k, B) and 0 < a₁ < … < a_n is a sequence of integers with a_n ? Bn, then some k of the a_i form an arithmetic progression. We prove that given any B and k, there is a number m(k, B) such that if m ? m(k, B) and u₀, u₁, …, u_m is a sequence of plane lattice points with ∑_i=1^m…u_i ? u_i?1… ? Bm, then some k of the u_i are collinear. Our result, while similar to Szemerédi's theorem, does not appear to imply it, nor does Szemerédi's theorem appear to imply our result.     

Some applications of Montgomery's sieve

Artin has conjectured that every positive integer not a perfect square is a primitive root for some odd prime. A new estimate is obtained for the number of integers in the interval [M + 1, M + N] which are not primitive roots for any odd prime, improving on a theorem of Gallagher.Erd?s has conjectured that 7, 15, 21, 45, 75, and 105 are the only values of the positive integer n for which n ? 2^k is prime for every k with 1 ≤ k ≤ log₂n. An estimate is proved for the number of such n ≤ N.     

Lucas's criterion for the primality of numbers of the form N = h2n−1

The following theorem is proved. Let N = h2ⁿ-1, where n ≥ 2, h is odd, 1 <-h < 2ⁿ, and suppose that v is a positive integer, v ≥ 3,α is a root of the equation $$(v^2 - 4,N) = 1,\left( {\frac{{v - 2}}{N}} \right) = 1,\left( {\frac{{v + 2}}{N}} \right) = - 1$$ . Then for N to be prime, it is necessary and sufficient that s_n?2≡0(modN), where S_k+1=S _k ² ? 2 (k = 0, 1...), s_o=a^h+ a^?h. For given N, an algorithm is described for the construction of the smallest v satisfying the conditions of this theorem.     

Erd?s-Zaks all divisor sets

Let ? _n be the finite cyclic group of order n and S ? ? _n . We examine the factorization properties of the Block Monoid B(? _n , S) when S is constructed using a method inspired by a 1990 paper of Erd?s and Zaks. For such a set S, we develop an algorithm in Section 2 to produce and order a set {M _i } _i=1 ^n?1 which contains all the non-primary irreducible Blocks (or atoms) of B(? _n , S). This construction yields a weakly half-factorial Block Monoid (see [9]). After developing some basic properties of the set {M _i } _i=1 ^n?1 , we examine in Section 3 the connection between these irreducible blocks and the Erd?s-Zaks notion of ??splittable sets.?? In particular, the Erd?s-Zaks notion of ??irreducible?? does not match the classic notion of ??irreducible?? for the commutative cancellative monoids B(? _n , S). We close in Sections 4 and 5 with a detailed discussion of the special properties of the blocks M1 with an emphasis on the case where the exponents of M ₁ take on extreme values. The work of Section 5 allows us to offer alternate arguments for two of the main results of the original paper by Erd?s and Zaks.     

Classifying Erdős type spaces of higher descriptive complexity

Let ${({E_n})_{n \in \omega }}$ be a sequence of zero-dimensional subsets of the reals, ?. The Erd?s type space ? corresponding to this sequence is defined by ? = {x ∈ ? ²: x _n ∈ E _n , n ∈ω}. The most famous examples are Erd?s space, with E _n equal to the rationals for each n, and complete Erd?s space, with E _n = {0} ∪ {1/m: m ∈ ?} for each n. If all sets E _n are ${G_\delta }$ and the space ? is not zero-dimensional, then ? is known to be homeomorphic to complete Erd?s space, and if all sets E _n are ${F_{\sigma \delta }}$ , then under a mild additional condition ? is known to be homeomorphic to Erd?s space. In this paper we investigate the situation where all sets E _n are Borel sets in the same multiplicative class. Many of these spaces can be linked to the Erd?s type space with all sets E _n equal to the element of that multiplicative Borel class which absorbs the class. Furthermore, we introduce coanalytic Erd?s space and we establish a link between this space and homeomorphism groups of manifolds that leave the zero-dimensional pseudoboundary invariant. The general framework that we develop gives analogous results for nonseparable Erd?s type spaces.     

A binary linear recurrence sequence of composite numbers

Let (a,b)∈Z², where b≠0 and (a,b)≠(±2,−1). We prove that then there exist two positive relatively prime composite integers x₁, x₂ such that the sequence given by xn+1=axn+bxn−1, n=2,3,… , consists of composite terms only, i.e., |xn| is a composite integer for each n∈N. In the proof of this result we use certain covering systems, divisibility sequences and, for some special pairs (a,±1), computer calculations. The paper is motivated by a result of Graham who proved this theorem in the special case of the Fibonacci-like sequence, where (a,b)=(1,1).     

Invariance principles for stochastic area and related stochastic integrals

Given an antisymmetric kernel K (K(z, z′) = ?K(z′, z)) and i.i.d. random variates Z_n, n?1, such that EK²(Z₁, Z₂)<∞, set A_n = ∑₁?i?j?nK(Z_i,Z_j), n?1. If the Z_n's are two-dimensional and K is the determinant function, A_n is a discrete analogue of Paul Lévy's so-called stochastic area. Using a general functional central limit theorem for stochastic integrals, we obtain limit theorems for the A_n's which mirror the corresponding results for the symmetric kernels that figure in theory of U-statistics.     

Generating non-jumping numbers recursively

Let r?2 be an integer. A real number α∈[0,1) is a jump for r if there is a constant c>0 such that for any ε>0 and any integer m where m?r, there exists an integer n₀ such that any r-uniform graph with n>n₀ vertices and density ?α+ε contains a subgraph with m vertices and density ?α+c. It follows from a fundamental theorem of Erd?s and Stone that every α∈[0,1) is a jump for r=2. Erd?s asked whether the same is true for r?3. Frankl and Rödl gave a negative answer by showing some non-jumping numbers for every r?3. In this paper, we provide a recursive formula to generate more non-jumping numbers for every r?3 based on the current known non-jumping numbers.     

Bilinear and quadratic variants on the Littlewood-Offord problem

If f(x ₁, …, x _n ) is a polynomial dependent on a large number of independent Bernoulli random variables, what can be said about the maximum concentration of f on any single value? For linear polynomials, this reduces to one version of the classical Littlewood-Offord problem: Given nonzero constants a ₁, …,a _n , what is the maximum number of sums of the form ±a ₁ ± a ₂ ± … ± a _n which take on any single value? Here we consider the case where f is either a bilinear form or a quadratic form. For the bilinear case, we show that the only forms having concentration significantly larger than n ^?1 are those which are in a certain sense very close to being degenerate. For the quadratic case, we show that no form having many nonzero coefficients has concentration significantly larger than n ^?1/2. In both cases the results are nearly tight.     

Properly coloured Hamiltonian cycles in edge-coloured complete graphs

Let K ^c _n be an edge-coloured complete graph on n vertices. Let Δ_mon(K^c _n) denote the largest number of edges of the same colour incident with a vertex of K^c _n. A properly coloured cycleis a cycle such that no two adjacent edges have the same colour. In 1976, BollobÁs and Erd?s[6] conjectured that every K^c _n with Δ_mon(K^c _n)<?n/2?contains a properly coloured Hamiltonian cycle. In this paper, we show that for any ε>0, there exists an integer n₀ such that every K^c _n with Δ_mon(K^c _n)<(1/2–ε)n and n≥n₀ contains a properly coloured Hamiltonian cycle. This improves a result of Alon and Gutin [1]. Hence, the conjecture of BollobÁs and Erd?s is true asymptotically.     

On a characterization of tridiagonal matrices by M. Fiedler

In this note two new proofs are given of the following characterization theorem of M. Fiedler: Let C_n, n?2, be the class of all symmetric, real matrices A of order n with the property that rank (A + D) ? n - 1 for any diagonal real matrix D. Then for any A ε C_n there exists a permutation matrix P such that PAP^T is tridiagonal and irreducible.     

On the difference between an integer and its m-th power mod n

For any real constants λ ₁, λ ₂ ∈ (0, 1], let $n \geqslant \max \{ [\tfrac{1} {{\lambda _1 }}],[\tfrac{1} {{\lambda _2 }}]\} $ , m ? 2 be integers. Suppose integers a ∈ [1, λ ₁ n] and b ∈ [1, λ ₂ n] satisfy the congruence b ≡ a ^m (mod n). The main purpose of this paper is to study the mean value of (a ? b)^2k for any fixed positive integer k and obtain some sharp asymptotic formulae.     

Integral Domains with Highly Nonunique Factorization

For a positive integer n, an atomic integral domain R is defined to be completely non- n- factorial if for any n atoms a₁…, a_n, the product a₁ … a _n has as highly nonunique a factorization into atoms as possible in that given any n ? 1 atoms b₁,…, b_{nt - 1}, b₁ … b _n? 1¦a₁ … a _n. We show that R is completely non-n-factorial for some n ≥ 2 if and only if (R, M) is a quasilocal domain with [M: M] a DVR having M as its maximal ideal.     

A Center Transversal Theorem for Hyperplanes and Applications to Graph Drawing

Motivated by an open problem from graph drawing, we study several partitioning problems for line and hyperplane arrangements. We prove a ham-sandwich cut theorem: given two sets of n lines in ?², there is a line ? such that in both line sets, for both halfplanes delimited by ?, there are $\sqrt{n}$ lines which pairwise intersect in that halfplane, and this bound is tight; a centerpoint theorem: for any set of n lines there is a point such that for any halfplane containing that point there are $\sqrt{n/3}$ of the lines which pairwise intersect in that halfplane. We generalize those results in higher dimension and obtain a center transversal theorem, a same-type lemma, and a positive portion Erd?s–Szekeres theorem for hyperplane arrangements. This is done by formulating a generalization of the center transversal theorem which applies to set functions that are much more general than measures. Back to graph drawing (and in the plane), we completely solve the open problem that motivated our search: there is no set of n labeled lines that are universal for all n-vertex labeled planar graphs. In contrast, the main result by Pach and Toth (J. Graph Theory 46(1):39–47, 2004), has, as an easy consequence, that every set of n (unlabeled) lines is universal for all n-vertex (unlabeled) planar graphs.     

When does the zero-one <Emphasis Type="Italic">k</Emphasis>-law fail?

The limit probabilities of the first-order properties of a random graph in the Erd?s–Rényi model G(n, n^?α), α ∈ (0, 1), are studied. A random graph G(n, n^?α) is said to obey the zero-one k-law if, given any property expressed by a formula of quantifier depth at most k, the probability of this property tends to either 0 or 1. As is known, for α = 1? 1/(2^k?1 + a/b), where a > 2^k?1, the zero-one k-law holds. Moreover, this law does not hold for b = 1 and a ≤ 2^k?1 ? 2. It is proved that the k-law also fails for b > 1 and a ≤ 2^k?1 ? (b + 1)².     

Some permutation problems

Put Z_n = {1, 2,…, n} and let π denote an arbitrary permutation of Z_n. Problem I. Let π = (π(1), π(2), …, π(n)). π has an up, down, or fixed point at a according as a < π(a), a > π(a), or a = π(a). Let $\text{A}\text{(r, s, t)}$ be the number of π ∈ Z_n with r ups, s downs, and t fixed points. Problem II. Consider the triple π^?1(a), a, π(a). Let R denote an up and F a down of π and let B(n, r, s) denote the number of π ∈ Z_n with r occurrences of π^?1(a)RaRπ(a) and s occurrences of π^?1(a)FaFπ(a). Generating functions are obtained for each enumerant as well as for a refinement of the second. In each case use is made of the cycle structure of permutations.     

Hensley?s problem for complex and non-Archimedean meromorphic functions

Büchi?s problem asks if there exists a positive integer M such that all x₁,…,xM∈Z satisfying the equations for all 3?r?M must also satisfy for some integer x. Hensley?s problem asks if there exists a positive integer M such that, for any integers ν and a, if ²(ν+r)−a is a square for 1?r?M, then a=0. It is not difficult to see that a positive answer to Hensley?s problem implies a positive answer to Büchi?s problem. One can ask a more general version of the Hensley?s problem by replacing the square by n-th power for any integer n?2 which is called the Hensley?s n-th power problem. In this paper we will solve Hensley?s n-th power problem for complex meromorphic functions and non-Archimedean meromorphic functions.