CANT 2011
New York Number Theory Seminar
Ninth Annual Workshop on
Combinatorial and Additive Number Theory
CUNY Graduate CenterMay 24-27, 2011

Abstracts of lectures
Paul Baginski, Université Claude Bernard Lyon, France“Factoring within arithmetic progressions”
Abstract: An arithmetic congruence monoid is an arithmetic progression Ma,b :=a + bN which is closed under multiplication. For this to be the case, the parametersmust satisfy a2 ≡ a mod b. Though these Ma,b are multiplicative subsemigroups ofN, their factorization properties differ greatly from the unique factorization one enjoys in N. We will give a survey of the factorization properties of these semigroups,
starting from the distribution of irreducibles and continuing to factorization theoretic invariants such as the elasticity and Delta set.
Mei-Chu Chang, University of California-Riverside“Character sums with smooth moduli”
Abstract: In this talk we will discuss short character sums for moduli with small
prime factors and sharpen some of the known estimates. In particular, we willrevisit the arguments of Graham-Ringrose and Postnikov. It is well known that
non-trivial estimates on short character sums are relevant in establishing density
free regions for the corresponding Dirichlet L-function.

Scott Chapman, Sam Houston State University“Factorizations of algebraic integers, block monoids and additive number theory”
Abstract: Let OK be the ring of integers in a finite extension of the rationals. Fundamental problems involving the factorizations of elements in OK into irreducibles
appear early in the Abstract Algebra curriculum. At a basic level, the usual technique for attacking such problems involves using the norm function. There is amuch deeper connection between factorizations of elements in OK and the classgroup of OK . We will explore this connection and show that it easily generalizes
to Dedekind and Krull domains. Implicit in this discussion is the introductionof a structure known as a Block Monoid. A well-known theorem of Geroldinger
constructs a monoid homomorphism from OK to an appropriately chosen Block
Monoid B which preserves lengths of factorizations of elements into products ofirreducibles. The analysis of the factorization properties of Block Monoids leads tothe study of two well-known arithmetic constants from Additive Number Theory,
the Davenport Constant and the Cross Number.
1

Jonathan Cutler, Montclair State University“Extremal problems for homomorphisms”
Abstract: Interest in the number of independent sets in graphs can be traced backto Dedekind’s problem of 1897, which asked for the number of antichains in the
Boolean lattice. More recently, Alon gave an asymptotic upper bound on the number of independent sets in regular graphs, which is related to the number of sum-freesubsets in a group. Kahn improved this bound to a sharp one for bipartite regulargraphs and Zhao extended this to all regular graphs. In this talk, we will consider
problems related to the number of independent sets in graphs with a fixed numberof vertices and edges. Independent sets in a graph correspond exactly to homomorphisms into a path of length one, with one looped vertex. We find the graphs on a
fixed number of vertices and edges which maximize the number of homomorphisms
into this and some other small image graphs.
(Joint work with Jamie Radcliffe.)

Matthew DeVos, Simon Fraser University
Talk 1: “Transforms and Kneser’s addition theorem in groups”
Abstract: The Cauchy-Davenport Theorem gives a natural lower bound on the sizeof a sumset in the group Zp for p prime. There are a variety of proofs of this result,but perhaps the simplest is based on the uncrossing transform which takes a pairof sets A, B and replaces them by their intersection and union. Kneser generalized
this result to arbitrary abelian groups using a related operation called Dyson’s etransform. Here we shall discuss these and other transforms, and give a new proofof Kneser’s theorem based on the uncrossing transform.
Talk 2: “A generalization of Kneser’s theorem to nonabelian groups”
Abstract: Vosper characterized the tight instances of the Cauchy-Davenport theorem, and Kempermann proved a rather complicated theorem which characterized
the tight instances of Kneser’s addition theorem. Here we present a generalization of these results to the nonabelian case by giving a complete characterizationof all pairs of finite nonempty sets A, B in a (multiplicative) group which satisfy|AB| < |A| + |B|. As a corollary of this we obtain a generalization of Kneser’s
theorem to nonabelian groups.
Talk 3: “Toward the Schrijver-Seymour Conjecture”
Abstract: A well-known theorem due to Erdős, Ginzburg, and Ziv asserts that every sequence of length 2n − 1 from an abelian group of order n has a subsequenceof length n which sums to 0. A related result due to Bialstocki and Dierker (later
generalized by Kleitman and Furedi) asserts that whenever p is prime and the edgesof the complete graph on p + 1 vertices are labelled with elements of the group Zp ,there exists a spanning tree so that the sum of the labels on its edges is 0. In afascinating paper, Schrijver and Seymour found a common generalization of theseresults to the setting of vector spaces (or more generally matroids). They provea theorem for the group Zp which generalizes Cauchy-Davenport and both of theresults mentioned above, and they conjecture a generalization of this to arbitrary

abelian groups. Here we shall discuss this conjecture and some recent progress toward it. This is joint with Goddyn and Mohar.
Talk 4: “Small separations in vertex-transitive graphs”
Abstract: The Cauchy-Davenport theorem has the following reformulation in termsof Cayley graphs: If p is prime, every Cayley graph on Zp with outdegree d isstrongly d-connected. Numerous related theorems show that finite graphs withcertain transitivity properties are well connected. Here we present a rough structure
theorem for vertex separations of fixed size in an arbitrary vertex transitive graph.
We show that any such separation either only splits off a small amount, or thegraph has a cyclic structure. This gives a new proof of the structure of groups withlinear growth, and suggests further possibilities for generalizing Gromov’s theoremon growth. This is joint work with Mohar.

Aviezri S. Fraenkel, Weizmann Institute of Science, Israel“Aperiodic subtraction games”
Abstract: Periodicity is a fundamental property of many combinatorial games. It
is sought vigorously, yet remains elusive in important cases, such as for some octal
games, notably Grundy’s game. Periodicity is important, because it provides polytime winning strategies for many games. But subtraction games, impartial andpartizan, have been proved to be periodic. Our main purpose here is to exhibit
constructively a class of subtraction games which is demonstratively aperiodic andyet is shown to have linear-time winning strategies.

Peter Hegarty, Chalmers University of Technology and University of Gothenburg,
Sweden“Sumsets, exponents and growth of graph powers”
Abstract: This talk will be an update on a topic I introduced at last year’s workshop, describing recent advances, remaining open problems and a wider context
for the subject matter. The basic idea is to observe that growth of iterated sumsets in an abelian group corresponds to growth of powers of the associated Cayley
graphs, and then ask to what extent properties of sumsets are inherited by moregeneral graphs. This leads to a rich collection of questions, some of which havebeen answered (via “non-trivial” theorems) and some not.

Charles Helou, Pennsylvania State University - Brandywine“Representations by near quadratic sequences”
Abstract: We prove that if A = {a1 < a2 < · · · < an < . . . } is an infinite setof natural numbers whose general term an is close to that of a quadratic sequence{pn2 +qn+r : n ≥ 1} with rational coefficients p, q, r, in the sense that the difference|pn2 + qn + r − an | is bounded (for n ≥ 1), then the number of representations ofintegers by A is unbounded. We first establish that, if e is a positive integer, then thenumber of representations of natural numbers by the quadratic form x2 + ey 2 , withx and y lying in arithmetic progressions, is unbounded (working in the quadratic√field Q( −e)). This is then extended to binary quadratic forms ax2 + by 2 , andapplied to obtain the desired result. We also establish related properties for the
integral parts of some sequences of real numbers.
(Joint work with L. Haddad).

Jerry Hu, University of Houston-Victoria“The probability that m positive integers are k-wise relatively prime”
Abstract: The finite set of integers {a1 , a2 , ..., am } is k-wise relatively prime ifevery subset of size k is relatively prime. In this talk we will discuss how to findthe probability that m positive integers are k-wise relatively prime. In particular,
we will demonstrate our method for the case k = 3. The case k = 2 was solved by
L. Tóth in 2002.

Alex Iosevich, University of Rochester“Sum-product theory over Zpl ”
Abstract: Over the past few years, much work has been done to obtain concrete
exponents for the sum-product and distance set problems in vector spaces over finite
fields. In this talk we shall discuss this problem in the realm of Zpl . Connections
with coloring problems for graphs will also be examined.
(Joint work with David Covert and Jonathan Pakianathan.)Renling Jin, College of Charleston“One set fits all”
Abstract: We discuss the idea of constructing a set A of natural numbers suchthat the lower Banach density, minimal density, lower asymptotic density, lower
logarithmic density, upper logarithmic density, upper asymptotic density, maximal
density, upper Banach density of A equal eight prescribed values α1 , α2 , . . . , α8 ,respectively, provided that0 6 α1 6 α2 6 · · · 6 α8 6 1 and α3 = α6 −→ α2 = α7 .
This is a part of a joint project with G. Grekos, et al.

Nathan Kaplan, Harvard University“Counting semigroups of genus g and Weierstrass semigroups of algebraic curves”
Abstract: Let n1 < n2 < · · · < nt be a finite set of natural numbers. We define
the numerical semigroup generated by these ni as the set of all natural numbers
which can be written as linear combinations of these generators with nonnegative
coefficients, and denote it by S = {k1 n1 + · · · + kt nt |ki ∈ N0 }. When the numbers
ni do not all share a common factor, it is easy to see that N \ S is a finite set, which
we call the gaps of S. We call the largest gap the Frobenius number of S, denoted
F (S), and the number of gaps, denoted g(S), is the genus of S.
Let N (g) be the number of semigroups of genus g. Several recent papers havestudied this function, and Zhai has recently proved a conjecture of Bras-Amorós,that it is asymptotic to ϕg , where ϕ is the golden ratio. It also appears that
N (g) ≤ N (g + 1), but this is only a conjecture.
In this talk we will overview what is known about N (g) and we will also discuss
a connection to algebraic geometry. On an algebraic curve C, there is a semigroupattached to each point P . The semigroup comes from rational functions on C whichhave poles only at P . Hurwitz has asked for a characterization of the semigroups
which occur as these Weierstrass semigroups of points, Buchweitz has given a necessary combinatorial condition for a semigroup to arise, and Komeda suggested the
problem of studying the density of semigroups of genus g which fail this Buchweitz
criterion. We will use recent results about N (g) to attack this question.

Mizan R. Khan, Eastern Connecticut State University“Revisiting Toom’s proof of Bulgarian Solitaire”
Abstract: We will discuss Andrei Toom’s proof of Bulgarian Solitaire that appearedin 1981 in Kvant, and show how an application of the Chinese Remainder Theorem
allows us to generalize the proof.
(Joint work with Therese Hart and Gabriel Khan.)Omar Kihel, Brock University, Canada“On permutation binomials over finite fields”
Abstract: Let Fq be the finite field of characteristic p containing q = pr elements. A
polynomial f (x) ∈ Fq is called a permutation polynomial of Fq if the induced map
f : Fq → Fq is one to one. The study of permutation polynomials goes back to Hermite for Fp and Dickson for Fq . The interest on permutation polynomials increasedin part because of their application in cryptography and coding theory. Despite theinterest of numerous people on the subject, characterizing permutation polynomials
and finding new families of permutation polynomials remain open questions. In thistalk, we will present a theorem that improve certain results of Masuda and Zieve,
Wan, and Turnwald and prove in particular that if f (x) = axn + xm permutes Fp ,where n > m > 0 and a ∈ Fp ∗ , then p − 1 ≤ (d − 1)d, where d = gcd(n − m, p − 1),and that this bound of p in term of d only, is sharp. We show as well, that binomialsof certain shapes over Fq do not exist, and how to obtain in certain cases a new
permutation binomial over a subfield of Fq from a permutation binomial over Fq .

Alex Kontorovich, SUNY at Stony Brook“On Zaremba’s Conjecture”
Abstract: Inspired by the theory of good lattice points in numerical integration,
Zaremba conjectured in 1972 that for every denominator q, there is some coprime
numerator p, such that the continued fraction expansion of p/q has uniformly
bounded quotients. We will present recent progress on this problem.
(Joint work with Jean Bourgain.)Urban Larsson, Chalmers University of Technology and University of Gothenburg, Sweden“From heaps of matches to the limits of computability”
Abstract: We study so-called invariant games played with heaps of matches. For
an example of such a game suppose there are three heaps, and a legal move consistsin either removing three matches from heap A, or removing one match from heap B
and moving a match from heap C to heap A. Two players take turns, and a player
unable to make a move loses. We show that these innocent looking games embracecomputational universality, and that therefore a number of basic questions about
them are algorithmically undecidable.
(Joint work with Johan Wästlund, Chalmers University of Technology)

Thai Hoang Le, Institute for Advanced Study“Problems and results on intersective sets”
Abstract: In the late 70s, Furstenberg and Sárközy independently proved the following: If A is a subset of positive density of the integers, then there must be two
distinct elements of A whose difference is a perfect square. The same thing is true
if the set of squares is replaced by {p + 1 : p prime} or {p − 1 : p prime}. Motivatedby these results, we call a set H ⊂ Z+ intersective if (A − A) ∩ H 6= ∅ whenever A isa subset of positive density of Z. In this talk, I will survey results and questions on
intersective sets, with an emphasis on intersective sets with respect to the primes,
and intersective sets in the ring Fq [t] of polynomials over a finite field. In the latter setting, sometimes better results are obtained, but sometimes extra difficulties
arise.

Vsevolod F. Lev, University of Haifa“Doubling-critical sets in binary spaces”
Abstract: We say that a subset A of an abelian group is doubling-critical if, forany proper subset B ⊂ A, we have 2B 6= 2A; that is, removing any element from A
affects its doubling 2A. Motivated by applications in finite geometries, we determine
the largest possible size of a doubling-critical set in an elementary abelian 2-group,and give a complete classification of all ”large” doubling-critical sets. (The talk isbased on a joint paper with David Grynkiewicz.)

Željka Ljujić, CUNY Graduate Center“A lower bound for the size of a sum of dilates”
Abstract: Let A be a subset of integers and let 2·A+k·A = {2a1 +ka2 : a1 , a2 ∈ A}.
Y. O. Hamidoune and J. Rué proved in that if k is an odd prime and A a finite setof integers such that |A| > 8k k , then |2 · A + k · A| ≥ (k + 2)|A| − k 2 − k + 2. In thistalk, I will show how this result can be extended to the case when k is a power ofan odd prime or product of two primes.

Neil Lyall, University of Georgia“Polynomial patterns in subsets of the integers”
Abstract: We will present a new proof of a striking and elegant fact (originallyestablished independently by Furstenberg and Sarkozy) that any subset of the integers of positive upper density necessarily contains two distinct elements whose
difference is given by a perfect square. If time permits we may also discuss a numberof variations, extensions and generalizations of this result.

Steven J. Miller, Williams College“Cookie Monster Meets the Fibonacci Numbers, II. Mmmmmm – Theorems!”
Abstract: A beautiful theorem of Zeckendorf states that every positive integer
can be written uniquely as a sum of non-consecutive Fibonacci numbers. Once
this has been shown, it is natural to ask how many Fibonacci numbers are needed.
Lekkerkerker proved that the average number of such summands needed for integers
in [Fn , Fn+1 )isn/(φ2 + 1), where φ is the golden mean. We present a combinatorial
proof of this through the cookie problem and differentiating identities, and further
prove that the fluctuations about the mean are normally distributed. These techniques apply to numerous generalizations, which we’ll discuss.
(Joint work with Murat Kologlu, Gene Kopp and Yinghui Wang.)

Steven J. Miller, Sean C. Pegado, Sidney Luc Robinson, Williams College“Explicit Constructions of Generalized MSTD Sets”
Abstract: We generalize the construction of Miller, Orosz and Scheinerman andexplicitly construct a large family of sets A with |A+A+A+A| > |(A+A)−(A+A)|
and show that the density of sets A ⊂ [1, n] satisfying this condition is at least Cnr ,where r = 16/ log2 (256/255) ≈ .001. We also construct, for each integer k, a set A
such that |4A| − |2A − 2A| = k.

Rishi Nath, York College (CUNY)“Simultaneous core partitions”
Abstract: p-core partitions are partitions which contain no hook of a fixed length p.
They arise in various areas including the block theory of symmetric groups, k-Schurfunctions, Shi arrangements and Coxeter groups. Here we survey new research into
simultaneous core partitions, that is, those containing no hooks for two distinct
integers p and q. The work of J. Olsson, M. Fayers, and others will be discussed.

Melvyn B. Nathanson, Lehman College (CUNY)“Hamidoune’s method in additive number theory”
Abstract: This will be a survey of some of Hamidoune’s methods and results inadditive number theory.

Hoi H. Nguyen, University of Pennsylvania“Inverse Littlewood-Offord theorems for quadratic forms and the singularity of
random symmetric matrices”
Abstract: The inverse Littlewood-Offord theorems for linear forms seem to be usefulfor the task of estimating the singularity of random matrices. In this talk I will
give an inverse version for quadratic forms and deduce from it some new bounds
on the singularity of random symmetric matrices.”

Lan Nguyen“On the Grothendieck group associated to quantum arithmetic”
Abstract: In this talk, we discuss our results concerning the Grothendieck groupassociated to the solutions of certain functional equations arising from quantum
arithmetic. These results resolve a problem raised by Melvyn Nathanson.

Neil Lyall, University of Georgia“Polynomial patterns in subsets of the integers”
Abstract: We will present a new proof of a striking and elegant fact (originallyestablished independently by Furstenberg and Sarközy) that any subset of the integers of positive upper density necessarily contains two distinct elements whose
difference is given by a perfect square. If time permits we may also discuss a numberof variations, extensions and generalizations of this result.

Giorgis Petridis, University of Cambridge“The Plünnecke-Ruzsa inequality”
Abstract: In this series of lectures we will study in detail the Plünnecke-Ruzsa
inequality. Roughly speaking it asserts that if A + A has size comparable to A, thenso does the sum-difference set kA−lA. The precise statement is as follows. Let A bea set in an Abelian group. Suppose that |A + A| ≤ α|A|. Then |kA − lA| ≤ αk+l |A|.
The inequality follows from a statement about the growth of a class of directed
layered graphs. Our first task will be to present a new proof of the graph-theoretic
inequality that is inspired by Plünnecke’s and Ruzsa’s work, but is simpler. We
will also explain why the inequality is best possible and use a simple probabilistic
argument to construct extremal graphs on which it is attained.
Next we will present a more direct and purely combinatorial proof of the PlünneckeRuzsa inequality that avoids any graph theory. One of the key features is that the
combinatorial method works equally well in the non-Abelian setting. This is somewhat surprising as commutativity plays a vital role in the graph-theoretic proof.
We will thus derive a short proof of a non-Abelian generalisation of the PlünneckeRuzsa inequality first proved by Tao.
Lastly we will study the growth of higher sumsets when a different set B isadded to A. Ruzsa has shown that |A + B| ≤ α|A| implies |A + 2B| ≤ α3/2 |A|.
His method works equally well for higher sumsets and gives |A + hB| ≤ α2−1/h |A|,
which is best possible in terms of α and |A|. We will introduce a further dependence
on h by showing |A + hB| ≤ α2−1/h |A|/h2 . The improvement is modest, but isnonetheless worthwhile for the following reason. Most upper bounds in the area
are of multiplicative nature. By this one means that passing from A and B to
the tensor products Ar and B r preserves the upper bound. This is because |A|,
|A + hB| and α are replaced by their rth powers. The Plünnecke-Ruzsa inequality
shares this feature as well. The stronger upper bound on |A + hB| we will present
does not because of the further dependence on h. Given that there are sets where|A + hB| ≥ α2−1/h /hh , such a result is a second step towards determining thecorrect answer to the problem
No prior knowledge of the material will be assumed. Along the way we will also
discuss natural problems that arise, though it must be pointed out that they aremostly of grapth-theoretical nature.

Steve Senger, University of Missouri“Consequences and connections of recent results in geometric combinatorics”
Abstract: We discuss a number of recent results in geometric combinatorics related
to the Guth-Katz resolution of the planar case of the Erdős distance problem, whichasks for the number of distinct distances determined by a large, finite point set.
In particular, we use a new theorem of Iosevich, Roche-Newton, and Rudnev on
the number of distinct dot products determined by a set of points in the plane toimprove higher dimensional dot product results as well as to guarantee a lack ofmultiplicative structure in sets of the form AA + 1.

Jonathan Sondow, New York
“Ramanujan primes: bounds, runs, twins, and gaps”
Abstract: The nth Ramanujan primeis the smallest positive integer Rn such that ifx ≥ Rn , then the interval 12 x, x contains at least n primes. In a paper to appear
in the Journal of Integer Sequences, John Nicholson, Tony Noe, and I sharpen
Laishram’s theorem that Rn < p3n by proving that the maximum of Rn /p3n is
R5 /p15 = 41/47. The proof uses another result of Laishram and a computation of
the first 169350 Ramanujan primes by Noe’s fast algorithm. We also give statistics
on the length of the longest run of Ramanujan primes among all primes p < 10n ,for n ≤ 9. We prove that if an upper twin prime is Ramanujan, then so is thelower; a table gives the number of twin primes below 10n of three types. Finally,
we relate runs of Ramanujan primes to prime gaps. Along the way, we state several
conjectures and open problems.