On sums and products in ℂ[<Emphasis Type="Italic">x</Emphasis>]

We prove that there exists an absolute constant c>0 such that if A is a set of n monic polynomials, and if the product set A.A has at most n ^1+c elements, then |A+A|≫n2. This can be thought of as step towards proving the Erdős–Szemerédi sum-product conjecture for polynomial rings. We also show that under a suitable generalization of Fermat’s Last Theorem, the same result holds for the integers. The methods we use to prove are a mixture of algebraic (e.g. Mason’s theorem) and combinatorial (e.g. the Ruzsa–Plunnecke inequality) techniques.     

Restricted sumsets and a conjecture of Lev

LetA, B, S be finite subsets of an abelian groupG. Suppose that the restricted sumsetC={α+b: α ∈A, b ∈B, and α − b ∉S} is nonempty and somec∈C can be written asa+b witha∈A andb∈B in at mostm ways. We show that ifG is torsion-free or elementary abelian, then |C|≥|A|+|B|−|S|−m. We also prove that |C|≥|A|+|B|−2|S|−m if the torsion subgroup ofG is cyclic. In the caseS={0} this provides an advance on a conjecture of Lev. This author is responsible for communications, and supported by the National Science Fund for Distinguished Young Scholars (No. 10425103) and the Key Program of NSF (No. 10331020) in China.     

Translation invariance in groups of prime order

We prove that there is an absolute constant c>0 with the following property: if Z/pZ denotes the group of prime order p, and a subset A⊂Z/pZ satisfies 1<|A|<p/2, then for any positive integer there are at most 2m non-zero elements b∈Z/pZ with |(A+b)?A|?m. This (partially) extends onto prime-order groups the result, established earlier by S. Konyagin and the present author for the group of integers. We notice that if A⊂Z/pZ is an arithmetic progression and m<|A|<p/2, then there are exactly 2m non-zero elements b∈Z/pZ with |(A+b)?A|?m. Furthermore, the bound c|A|/ln|A| is best possible up to the value of the constant c. On the other hand, it is likely that the assumption can be dropped or substantially relaxed.     

Linear equations and sets of integers

We prove two results concerning solvability of a linear equation in sets of integers. In particular, it is shown that for every k∈ℕ, there is a noninvariant linear equation in k variables such that if A⫅{1,…,N} has no solution to the equation then |A|\leqq 2^-ck/(logk)2N|A|\leqq 2^{-ck/{(\log k)}^{2}}N, for some absolute constant c>0, provided that N is large enough.     

Palindromes in Lucas Sequences

 In this paper, we show that if (u _n ) _n ≥ 0 is a Lucas sequence of integers whose roots are real quadratic units (like the Fibonacci sequence, for example), then for every integer b > 1 the density of the set of positive integers n such that |u _n | is a base b palindrome (i.e., the string of its base b digits reads the same from the left and from the right) is zero.     

SCORE LISTS IN （h, k）-BIPARTITE HYPERTOURNAMENTS

Given non-negative integers m,n,h and k with m ≥ h ＞ 1 and n ≥ k ＞ 1, an (h, k)-bipartite hypertournament on m n vertices is a triple (U, V, A), where U and V are two sets of vertices with |U| = m and |V| = n, and A is a set of (h k)-tuples of vertices,called arcs, with at most h vertices from U and at most k vertices from V, such that for any h k subsets U1 ∪ V1 of U ∪ V, A contains exactly one of the (h k)! (h k)-tuples whose entries belong to U1 ∪ V1. Necessary and sufficient conditions for a pair of non-decreasing sequences of non-negative integers to be the losing score lists or score lists of some(h, k)-bipartite hypertournament are obtained.     

Lower bound on the profile of degree pairs in cross-intersecting set systems

We raise the following problem. For natural numbers m, n ≥ 2, determine pairs d′, d″ (both depending on m and n only) with the property that in every pair of set systems A, B with |A| ≤ m, |B| ≤ n, and A ∩ B ≠ 0 for all A ∈ A, B ∈ B, there exists an element contained in at least d′ |A| members of A and d″ |B| members of B. Generalizing a previous result of Kyureghyan, we prove that all the extremal pairs of (d′, d″) lie on or above the line (n − 1) x + (m − 1) y = 1. Constructions show that the pair (1 + ɛ / 2n − 2, 1 + ɛ / 2m − 2) is infeasible in general, for all m, n ≥ 2 and all ɛ > 0. Moreover, for m = 2, the pair (d′, d″) = (1 / n, 1 / 2) is feasible if and only if 2 ≤ n ≤ 4. The problem originates from Razborov and Vereshchagin’s work on decision tree complexity. Research supported in part by the Hungarian Research Fund under grant OTKA T-032969.     

Palindromes in Lucas Sequences

 In this paper, we show that if (u _n ) _n ≥ 0 is a Lucas sequence of integers whose roots are real quadratic units (like the Fibonacci sequence, for example), then for every integer b > 1 the density of the set of positive integers n such that |u _n | is a base b palindrome (i.e., the string of its base b digits reads the same from the left and from the right) is zero. Received October 30, 2001; in revised form March 4, 2002     

Large centralizers in finite solvable groups

In 1955 R. Brauer and K. A. Fowler showed that ifG is a group of even order >2, and the order |Z(G)| of the center ofG is odd, then there exists a strongly real) elementx∈G−Z whose centralizer satisfies|C _G(x)|>|G|^1/3. In Theorem 1 we show that every non-abeliansolvable groupG contains an elementx∈G−Z such that|C _G(x)|>[G:G′∩Z]^1/2 (and thus|C _G(x)|>|G|^1/3). We also note that if non-abelianG is either metabelian, nilpotent or (more generally) supersolvable, or anA-group, or any Frobenius group, then|C _G(x)|>|G|^1/2 for somex∈G−Z. In Theorem 2 we prove that every non-abelian groupG of orderp ^mqⁿ (p, q primes) contains a proper centralizer of order >|G|^1/2. Finally, in Theorem 3 we show that theaverage |C(x)|, x∈G, is ≧c|G| ^1/3 for metabelian groups, wherec is constant and the exponent 1/3 is best possible.     

Counting points in hypercubes and convolution measure algebras

It is shown that ifA andB are non-empty subsets of {0, 1} ⁿ (for somenεN) then |A+B|≧(|A||B|)^α where α=(1/2) log₂ 3 here and in what follows. In particular if |A|=2 ^n-1 then |A+A|≧3 ^n-1 which anwers a question of Brown and Moran. It is also shown that if |A| = 2 ^n-1 then |A+A|=3 ^n-1 if and only if the points ofA lie on a hyperplane inn-dimensions. Necessary and sufficient conditions are also given for |A +B|=(|A||B|)^α. The above results imply the following improvement of a result of Talagrand [7]: ifX andY are compact subsets ofK (the Cantor set) withm(X),m(Y)>0 then λ(X+Y)≧2(m(X)m(Y))^α wherem is the usual measure onK and λ is Lebesgue measure. This also answers a question of Moran (in more precise terms) showing thatm is not concentrated on any proper Raikov system.     

Positivity Preserving Hadamard Matrix Functions

For every positive real number p that lies between even integers 2(m − 2) and 2(m − 1) we demonstrate a matrix A = [a_ij] of order 2m such that A is positive definite but the matrix with entries |a_ij|^p is not.     

The abc-conjecture for Algebraic Numbers

The abe-conjecture for the ring of integers states that, for every ε 〉 0 and every triple of relatively prime nonzero integers （a, b, c） satisfying a ＋ b = c, we have max（｜a｜, ｜b｜, ｜c｜） 〈 rad（abc）^1＋ε with a finite number of exceptions. Here the radical rad（m） is the product of all distinct prime factors of m. In the present paper we propose an abe-conjecture for the field of all algebraic numbers. It is based on the definition of the radical （in Section 1） and of the height （in Section 2） of an algebraic number. From this abc-conjecture we deduce some versions of Fermat＇s last theorem for the field of all algebraic numbers, and we discuss from this point of view known results on solutions of Fermat＇s equation in fields of small degrees over Q.     

Eventually areally meanp-valent functions

Theorems concerning areally meanp-valent functions are extended to eventually areally meanp-valent functions. In particular, suppose is eventually areally meanp-valent in the unit disc,b, c are positive integers,a≧max {p−1, 0}. If |a _n|≦Cn ^α for alln=bm+c,m=1, 2, …, then |a _n|≦C′n ^α for alln. This is a marked extension of results due to Goluzin and to Hayman.     

On critical Fujita exponents for heat equations with nonlinear flux conditions on the boundary

We consider nonnegative solutions of initial-boundary value problems for parabolic equationsu _t=u_xx, u_t=(u^m)_xxand (m>1) forx>0,t>0 with nonlinear boundary conditions−u _x=u^p,−(u ^m)_x=u^pand forx=0,t>0, wherep>0. The initial function is assumed to be bounded, smooth and to have, in the latter two cases, compact support. We prove that for each problem there exist positive critical valuesp ₀,p_c(withp ₀<p_c)such that forp∃(0,p ₀],all solutions are global while forp∃(p₀,p_c] any solutionu≢0 blows up in a finite time and forp>p _csmall data solutions exist globally in time while large data solutions are nonglobal. We havep _c=2,p _c=m+1 andp _c=2m for each problem, whilep ₀=1,p ₀=1/2(m+1) andp ₀=2m/(m+1) respectively. This work was done during visits of the first author to Iowa State University and the Institute for Mathematics and its Applications at the University of Minnesota. The second author was supported in part by NSF Grant DMS-9102210.     

Isometric approximation property in euclidean spaces

We give a necessary and sufficient quantitative geometric condition for a compact setA⊂R ⁿ to have the following property with a givenc≥1: For everyɛ>0 and for every mapf: A→R ⁿ such that there is an isometryS: A→R ⁿ such that |Sx−fx|≤cɛ for allx∈A.     

On the Terai-Jésmanowicz conjecture

In this paper, we prove that if a, b and c are pairwise coprime positive integers such that a^2＋b^2=c^r,a〉b,a≡3 （mod4）,b≡2 （mod4） and c-1 is not a square, thena a^x＋b^y=c^z has only the positive integer solution （x, y, z） = （2, 2, r）.
Let m and r be positive integers with 2｜m and 2 r, define the integers Ur, Vr by （m ＋√-1）^r=Vr＋Ur√-1. If a = ｜Ur｜,b=｜Vr｜,c = m^2＋1 with m ≡ 2 （mod 4）,a ≡ 3 （mod 4）, and if r 〈 m/√1.5log3（m^2＋1）-1, then a^x ＋ b^y = c^z has only the positive integer solution （x,y, z） = （2, 2, r）. The argument here is elementary.     

A Neighborhood Condition for Graphs to Have [a, b]-Factors II

 Let a, b, m, and t be integers such that 1≤a<b and 1≤t≤⌉(b−m+1)/a⌉. Suppose that G is a graph of order |G| and H is any subgraph of G with the size |E(H)|=m. Then we prove that G has an [a,b]-factor containing all the edges of H if the minimum degree is at least a, |G|>((a+b)(t(a+b−1)−1)+2m)/b, and |N _G (x ₁)∪⋯ ∪N _G (x _t )|≥(a|G|+2m)/(a+b) for every independent set {x ₁,…,x _t }⊆V(G). This result is best possible in some sense and it is an extension of the result of H. Matsuda (A neighborhood condition for graphs to have [a,b]-factors, Discrete Mathematics 224 (2000) 289–292). Received: October, 2001 Final version received: September 17, 2002 RID="*" ID="*" This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Encouragement of Young Scientists, 13740084, 2001     

On cardinality constrained cycle and path polytopes

Given a directed graph D = (N, A) and a sequence of positive integers ${1 \leq c_1 < c_2 < \cdots < c_m \leq |N|}Given a directed graph D = (N, A) and a sequence of positive integers 1 ￡ c₁ < c₂ < ? < c_m ￡ |N|{1 \leq c_1 < c_2 < \cdots < c_m \leq |N|}, we consider those path and cycle polytopes that are defined as the convex hulls of the incidence vectors simple paths and cycles of D of cardinality c _p for some p ? {1,?,m}{p \in \{1,\ldots,m\}}, respectively. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. These inequalities can simply be transformed into inequalities that characterize the integer points of the undirected counterparts of cardinality constrained path and cycle polytopes. Beyond we investigate some further inequalities, in particular inequalities that are specific to odd/even paths and cycles.     

How many elements are needed to generate a finite group with good probability?

We prove that for any real number 0<α<1, there exists a constantc _α such that the probability of generating a finite groupG with [d(G)+c _α log log |G| log log log |G|] elements is at least α.