COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15
STEVEN J. MILLERA BSTRACT. These notes are a summary of the problem session discussions at various CANT (Combinatorial
and Additive Number Theory Conferences). Currently they include all years from 2009 through 2015 (inclusive); the goal is to supplement this file each year. These additions will include the problem session notes fromthat year, and occasionally discussions on progress on previous problems. If you are interested in pursuing anyof these problems and want additional information as to progress, please email the author.
For more information, visit the conference homepage at
http://www.theoryofnumbers.com/
or email either the typist at sjm1@williams.edu or Steven.Miller.MC.96@aya.yale.edu, or the organizer at
melvyn.nathanson@lehman.cuny.edu.
Warning: Many of these notes were LaTeX-ed in real-time by Steven J. Miller; all errors should be
attributed solely to him.

The typist was supported by NSF grants DMS0600848, DMS0600848 and DMS1265673. These notes
would not have been possible without the help of the participants, especially Kevin O’Bryant, my students,
especially Olivia Beckwith, Alan Chang, Ginny Hogan, Jasmine Powell, Ryan Ronan, Maddie Weinsteinand of course the organizer Mel Nathanson.
C ONTENTS
2009. CANT Problem Session: 20092009.1. Problem Session I: Tuesday, May 26th (Chair Kevin O’Bryant)2009.2. Problem Session II: Wednesday, May 27th
2009.3. Problem Session III: Thursday, May 28th
2009.4. Problem Session IV: Saturday, May 30
2009.5. Speakers and Participants Lists
2010. CANT Problem Session: 20102010.1. Problem Session III: Friday, May 28th (Chair)2010.2. Problem Session IV: Saturday, May 29th
2010.3. Speaker List
2011. CANT Problem Session: 20112011.1. Problem Sessions
2011.2. Speaker List
2012. CANT Problem Session: 20122012.1. Problem Session I: Tuesday, May 22nd (Chair Renling Jin)
2012.2. Problem Session II: Wednesday, May 23rd (Chair Steven J Miller)
2012.3. Problem Session III: Thursday, May 24th (Chair Alex Iosevich)2012.4. Problem Session IV: Friday, May 25th (Chair Kevin O’Bryant)2012.5. Speaker List
2013. CANT Problem Session: 20132013.1. Problem Session I: Tuesday, May 21st (Chair Steven Miller)
2013.2. Problem Session II: Wednesday, May 23rd (Chair Seva Lev)
2013.3. Problem Session III: Thursday, May 24th (Chair Kevin O’Bryant)2013.4. Problem Session IV: Friday, May 24th (Chair Renling Jin)
1

3
3
5
7
8
9
11
11
13
14
15
15
17
19
19
20
21
23
24
25
25
26
27
27

2

MILLER

2013.5. Additional Problems
2013.6. Speaker List
2014. CANT Problem Session: 20142014.1. Problem Session I: Wednesday, May 28th (Chair Steven J Miller)
2014.2. Problem Session II: Thursday, May 29th (Chair Kevin O’Bryant)2014.3. Problem Session III: Friday, May 24th (Chair Mel Nathanson)
2014.4. Speaker List
2015. CANT Problem Session: 2015
2015.1. Phase Transitions in MSTD sets: Steven J Miller
2015.2. An accidental sequence: Satyanand Singh2015.3. Kevin O’Bryant
2015.4. Steven Senger (repeat from previous years):2015.5. Nathan Kaplan:
2015.6. Nathan Kaplan (repeat from previous years):2015.7. Kevin O’Bryant:
2015.8. Speaker List

28
28
30
30
30
31
32
33
33
33
33
33
33
34
34
35

COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

3

Observed ΓHk,nL

0.60
0.55
0.50
0.45
k
20

40

60

80

100

F IGURE 1. Observed γ(k, 100), random sample 4458 MSTD sets.
2009. CANT P ROBLEM S ESSION : 20092009.1. Problem Session I: Tuesday, May 26th (Chair Kevin O’Bryant).
2009.1.1. Steven J Miller: I (sjm1@williams.edu). Probability an element is in an MSTD
Let γ(k, n) be the probability that k is in an MSTD set A with A ⊂ [0, n]; see for instance the figure
below

Conjecture: Fix a constant 0 < α < 1. Then limn→∞ γ(k, n) = 1/2 for ⌊αn⌋ ≤ k ≤ n − ⌊αn⌋.
Questions:• How big are the spikes? Do the sizes of the spikes tend to zero as n → ∞?
• Is the spike up equal to the spike down?
• Study more generally g(n) ≤ k ≤ n − g(n); is it sufficient for g(n) → ∞ monotonically at any
rate to have all k in the region above having probability 1/2 of being in an MSTD set? Can we takeg(n) = log log log n, or do we need g(n) = αn?
• A generic MSTD set has about n/2 elements; what other properties of a generic set are inherited by
an MSTD set?
• How big are the fluctuations in the middle?
• Do we want to look at all MSTD sets containing 1 and n, or do we want to just look at all subsets of[1, n] that are MSTD sets
Note since the end of the conference: Kevin O’Bryant has observations relevant to this and otherproblems proposed by Miller.
Note added in 2014: Many of these claims were later proved by Zhao.
2009.1.2. Steven J Miller: II (sjm1@williams.edu). With Dan S. and Brooke O. we constructed very densefamilies of MSTD sets in [0, r] such that these families were C/r 4 of all subsets of [0, r]. This isn’t a positive
percentage of sets, but it is significantly larger than any previous family. Can one do better? Can one get a
positive percentage?
2009.1.3. Peter Hegarty: I (hegarty@chalmers.se). Smallest size of an MSTD is 8 elements: A = {0, 2,
3, 4, 7, 10, 12, 14}; remove 4 and symmetric about 7. If look in Z2 , can construct an MSTD set of size 16
from this: take A × {0, 1} (any set of size two would work). Can you construct MSTD sets in Z2 without
going through an MSTD set in Z. Need a computer to show this set A was minimal (about 15 hours to find
all MSTD sets of size 8, and thus see that this set A is minimal). To find all MSTD sets up to isomorphismof a certain size is a finite computation, but practically impossible for 9.

4

MILLER

2009.1.4. Peter Hegarty: II (hegarty@chalmers.se). Question: What are the possible orders of a basis forZn ?
Let A ⊂ Zn . We say A is a basis of order h if hA = Zn but (h − 1)A 6= Zn . A is a basis of some order
if and only if (gcd(A), n) = 1.
A = {a1 , . . . , ak }, |hA| = O(k h ), order should be about log n/ log k, so k h = n. Order for a random
set to be a basis, should be of logarithmic order. Can write down a very inefficient basis where need longnsummands to cover all of Zn . To do this, take A = {0, 1, . . . , k − 1}. Order of this will be essentially k−1.
Conjecture: If the order of a basis is Θ(n) then the order must be very close to n/k for some k. So no
number between n/2 and n can be the order. Gives gaps. See paper by Dukes and Herke.
Question from participants: this can’t go on forever?
Answer from Peter: Can go on forever. Fix a k, let n → ∞, the way you would phrase to make it precise:n
Fix a k. For n ≫ 0 if the order of a basis is greater than k+1+ O(k) then the order must be within O(k) ofn/ℓ for some ℓ ≤ k.
Note : Since the end of the conference, Peter Hegarty has solved this problem. His result is available
at http://arxiv.org/abs/0906.5484
2009.1.5. Kevin O’Bryant (obryant@gmail.com). Take g0 = 0, gi to be the least positive integer such that
{g0 , g1 , . . . , gi } has no solutions to 5w + 2x = 5y + 2z. This is building a set greedily.
Let a0 = 0 andP
5 + 7 i−1
j=0 ajai = ⌊⌋.
(1)
2
Let A equal the sum of distinct ai ’s.
Conjecture: G = {5x + y : x ∈ A, 0 ≤ y ≤ 4}.
Appears computationally that there is some description of this sort when one number is at least twice aslarge as another; can replace (5, 2) with (11, 4) without trouble, but not with (4, 3).
Question from audience: Why 5 and 2?
Answer: 5, 2 smallest haven’t solved and have done the most computation.
Question from audience: How many other cases investigated?
Answer: Calculated all terms up to about 100,000 if both numbers at most 12 (and can exclude cases,
such as cases with common prime factors). Nice structure if one is twice the other, else irregular and nothing
to say (though all irregular in the same way).
2009.1.6. Ruzsa (through Simon Griffiths through Kevin O’Bryant). Let A ⊂ Z, |A| = n, andX
Sk = {
a : B ⊂ A, |B| = k}.
a∈BNote |Sk | = |Sn−k |. For example, if A = {1, 2, 4, 8, . . . , 2n−1 } then |Sk+1 | =Question: |Sk+1 | ≤ n−k
k+1 |Sk | whenever k < n/2?
2

Theorem (Ruzsa): Yes, when n > k +7k
2 .
n
Exercise: |Sk+1 | ≤ k+1|Sk |.

n 
n−kk+1 = k+1 |Sk |.

COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

52009.2. Problem Session II: Wednesday, May 27th.
2009.2.1. Comments after Nathanson’s Talk (Mel Nathanson:
melvyn.nathanson@lehman.cuny.edu). Paper is online at http://arxiv.org/pdf/0811.3990.
Take Gi with Ai of generators. Only one direct product, but many sets of generators that can constructfrom generators of individual groups. Could take direct product of generators. That’s complicated. Givengroups and generating sets, many ways to put together new sets of generators. Never thought about finitegroups because thinking about geometric group theory. For finite groups know at some point all spheres
empty.
Question: A result like this might not be true for semi-groups: bunch of things with finite spheres thenempty at some point. Additive sub-model of integers, all positive integers exceeding 1000. Can you have infinite sphere, finite sphere, infinite sphere, finite sphere.... Answer: don’t know. Wanted to create oscillatingsets of spheres, turned out couldn’t.
2009.2.2. Constructing MSTD Sets (Kevin O’Bryant, communicated to Steven Miller).
Theorem: di ∈ {3, 4, 5} independent uniformly distributed, x1 = 4, x2 = 5, xi = xi−1 + di ,A = {1} ∪ {0, ±x1 , . . . , ±xn }. Then |A + A| > |A − A| with probability 1.
Note
A+A
A−A
where X is the set of the xi ’s.

===(X + X) ∪ (X + 1) ∪ {2}(X − X) ∪ (X − 1) ∪ (1 − X) ∪ {0}(X + X) ∪ (X − 1) ∪ (1 + X) ∪ {0},2009.2.3. David Newman (davidsnewman@gmail.com). Suppose we have a basis for the non-negative integers, that is a set so that for any non-negative number we can find two elements of the set whose sum isthis given number. If we arrange the numbers in the set in ascending order then we can cut it off at a certain
point and look at the first N terms of this basis.
Question: Can this beginning of a basis be extended into a minimal basis? By minimal basis I mean abasis where if you remove any element it is no longer a basis.
Has to have 0 and 1 as a start. I think the answer is yes is because I haven’t seen the beginning of a basis
I couldn’t extend to a minimal basis. I have an algorithm implemented in Mathematica and in a few seconds
gives a set which is a minimal basis. That’s about all the info I have, other than one family of bases that I
can always extend to a minimal basis.
Another problem (from the theory of partitions): ConsiderX(1 + x)(1 + x2 ) · · · =an xn ,

which is the generating function for partitioning into distinct parts. Now put in minus signs:(1 − x)(1 − x2 ) · · · = 1 − x − x2 + x5 + x7 + · · · ,where all coefficients are in {0, ±1}. Now do partitions into unrestricted parts:
X(1 + x + x2 + x3 + · · · )(1 + x2 + x4 + x6 + · · · ) · · · =bn xn .
Question: can we change some of the signs above into minus signs so that the bn ’s are also in {0, ±1}.

6MILLER

Note since the conclusion of the conference: Peter Hegarty and David Newman have made progresson this. They are currently working on a paper: Let h > 1 be an integer, for any basis A for N0 oforder h and any n ∈ N0 the initial segment A ∩ [0, n] can be extend to a basis of A′ of order h whichis also a minimal asymptotic basis of this order.
2009.2.4. Infinitude of Primes (Steven Miller). Two types of proofs of the infinitude of primes, those thatgive lower bounds and those that don’t (such as Furstenberg’s topological proof). What category
Q doesζ(2) = π 2 /6 6= Q fall under? It implies there must be infinitely many primes, as this is ζ(2) = p (1 −p−2 )−1 ; if we knew how well π 2 can be approximated by rationals, we could convert this to knowledge
about spacings between primes. Unfortunately while we know the irrationality exponent for π 2 is at most
5.441243 (Rhin and Viola, 1996), their proof uses the prime number theorem to estimate lcm(1, . . . , n).
This leads to π(x) ≫ log log x/ log log log x infinitely often; actually, I can show: let g(x) = o(x/ log x)
then π(x) ≥ g(x). A preprint of my paper (with M. Schiffman and B. Wieland) is online at
http://arxiv.org/PS_cache/arxiv/pdf/0709/0709.2184v3.pdf
and I hope to have a final, cleaned up version in a few months. I’m looking for a proof of the finitenessof the irrationality measure of ζ(2) that doesn’t assume the prime number theorem. Note added in 2014:
Miller is currently working on this with some of his students.
2009.2.5. Kent Boklan (boklan@boole.cs.qc.edu). There are infinitely many primes, don’t know muchabout twin primes. Know sum of reciprocals of twins converges by Brun’s theorem. This is a hard theorem – I want to do elementary things. How do you show there are infinitely many primes which are nottwin primes. Trivial proof: There are infinitely many primes of the form 15k + 7 by Dirichlet, and not prime
if add or subtract 2. But Dirichlet isn’t elementary!
Pk
2009.2.6. Mel Nathanson II. A = {a1 , . . . , ak } finite set of integers, n =i=1 ai xi is solvable for alln if and only if gcd(A) = 1. In geometric group theory, can deduce algebraic properties of the group by
seeing how it acts on geometric objects. Fundamental lemma of geometric group theory says the following:
G is a group and acts on a set S (metric space), want action to be an isometry for any fixed g in the group.
Acts isometrically on the metric space S. Suppose the space is nice (Heine-Borel, want that: any closed
and bounded set is compact, call this a proper space). G acts properly discontinuously on X if intersection
non-empty for only finitely many g. Example: Zn acts on Rn by (g, x) = g + x. Have G\X, send x to its
orbit hxi. Put a quotient topology on G\X that makes projection map continuous. Example: Zn \Rn is then-torus. Let K ⊂ X compact, for every x ∈ X there is a y ∈ K such that gy = x. For example, n = 1:
Z acts on R by translation, take unit interval [0, 1] (compact), and every number is congruent modulo 1 tosomething in unit interval. The fundamental lemma of geometric group theory: Group acts as isometry andproperly discontinuously on proper metric space then G must be finitely generated. Know nothing about
if it is finitely or infinitely generated, but if acts geometrically in this nice way, that can only happen if thegroup is finitely generated. Proof goes by finding a compact set K with exactly the property above. What
we know about K since group action properly discontinuous, group action under K only finitely many, thatis a finite set of generators.
Suppose we specialize to elementary number theory: integers acting on reals by translations, compact set
K such that every real number is congruent modulo 1 to an element of K. Then we get a finite set of generators for the group, but the group is the integers and a finite set of integers is a finite set of relatively prime
integers. Get certain sets of relatively prime integers. What finite sets of integers can we get geometricallyin this way? Every finite set of relatively prime set of integers can be obtained this way. Curious thing isthat there is this geometric way to describe these sets. Look at lattice points in two dimensions, seems quite
complicated.
Article might be: http://arxiv.org/pdf/0901.1458.

COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

72009.3. Problem Session III: Thursday, May 28th.
2009.3.1. Gang Yu (yu@math.kent.edu). C ⊂ N is an infinite sequence, C(N ) = C ∩ [N ] (where [N ] ={0, . . . , N } or perhaps it starts at 1), h ≥ 2 fixed, call A ⊂ [N ] an h-basis of C(N ) if hA ⊃ C(N ).
Trivial estimate: |A| ≥ h!|C(N )|1/h .
Interesting cases: C is sparse but arithmetically nice:
C
C
C

=
=
=

{n2 }
{nα }
{f (n)}

where f is a degree 2 polynomial. Let|C(N )|,
N →∞ Dh (C, N )hΓh /C = lim

(2)

where
Dh (C, N ) =

min

A⊂[N]
A is an h−basis of C(N)

|A|.

(3)

Question: Is Γh (C) = 0 for polynomial C (ie, degree at least 2)?
Audience: Is it true for any sequence?
Gang:know. For AP = C, bounded away from 0. Specifically, A ⊂ [N ], A + A ⊃ {n2 : D ≤√ Don’t
1/4n ≤ N}, N= o(|A|)?
After the conference it was noted: Some information available at http://arxiv.org/pdf/
0711.1604.
2009.3.2. Simon Griffiths (sg332@cam.ac.uk). An n-sum of a sequence x1 , . . . , xr is a sum of the form
xi1 + · · · + xin where i1 < · · · < in , i.e. an element that can be obtained as the sum of an n-term
subsequence.
EGZ: Every sequence x1 , . . . , x2n−1 ∈ Zn has 0 as an n-sum.
Bollobás-Leader: Let x1 , . . . , xn+r ∈ G and suppose D is not ann-sum, then you have at least r + 1 n-sums.
Examples: EGZ is tight as demonstrated by the sequence of n − 1 0s and n − 1 1s; Bollobás-Leader istight as deomnstrated by the seq of n − 1 0s and r + 1 1s.
What about finite abelian groups more generally?
D(G) is Davenport constant, the minimum r where every r-term sequence has a non-trivial subsequencewith sum 0. For example: not difficult to show D(Zn ) = n.
Example: Let x1 , . . . , xD(G)−1 be a sequence in G with no non-trivial subsequence summing to 0, andadjoin n − 1 0s by setting xD(G) , ..., xn+D(G)−2 = 0. Then, by an easy check, we see that this sequence, oflength n + D(G) − 2 does not have 0 as an n-sum.
Gao: Every sequence x1 , . . . , xn+D(G)−1 has 0 as an n-sum.
Question: EGZ is to Bollobás-Leader as Gao is to ..?..?..
One Answer: A theorem of Gao and Leader.
Why do we need another answer: Both of the results, Bollobás-Leader and Gao-Leader allow us to see
the set of n-sums grow as the length of the underlying sequence increases. However perhaps in the case ofgeneral abelian groups there may be a different way to see this growth - to see this growth as a growth ofdimension in the sense described below.

8

MILLER

Our approach to defining the dimension of a subset S ⊂ G is similar to describing the dimension of asubspace via the maximum dimension of an independent subspace. Call a sequence zero-sum-free if nonon-trivial subsequence has sum 0. Let dim(S) equal D(G) minus the minimum r such that for every
zero-sum-free sequence. . , yr there exists an s ∈ S and a subsequence I such thaty1 , . P
s + I yi = 0.
If 0 ∈ S then we take the minimum to be zero. Thus,
Examples: dim(G) = D(G). S = G − {0} implies dim(S) = D(G) − 1. S = ∅ implies dim(S) = 0.
Conjecture: x1 , . . . , xn+r either 0 as an n-sum or dim ({n − SUMS}) ≥ r + 1.
2009.4. Problem Session IV: Saturday, May 30.
2009.4.1. Urban Larsson. How small can a maximal AP-free set be? Specifically, how large is the smallest
maximal (with respect to not having 3 terms in arithmetic progression) subset of [n]? Setµ(n) :=

min |A ∩ [n]| .

A
A is 3-free

Examples: The greedy subset of {0, 1, . . . } with 3-term APs is {n ∈ N : base-3 expansion of n has no ’2’s}.
This shows that µ(3t ) ≤ 2t . A better example is the set of natural numbers whose base-4 expansions haveneither ’2’s nor ’3’s. This gives µ(4t ) ≤ 2t .
Each pair of elements of A, which is 3-free, forbids at most three other numbers from A, so 3 |A|≥
2p√n − |A|, so that |A| ≥ c n. Attention to detail gives |A| ≥ 2n/3. If A is uniformly distributed
mod 4,pand u.d. in [n], then many pairs will not forbid√ three other numbers, and this gives |A| ≥ 420n/401.
I conjecture that µ(4t ) = 2t , and µ(n) ≥ n for all n.
2009.4.2. Renling Jin. Let d(A) = lim inf n→∞ A(n)/n be the lower asymptotic density of A, and let P
be the set of primes. Clearly∀A ⊆ N (d(A + P) ≥ f (d(A))

for f (x) = x. What is the right f ?
Using Plünnecke and d(3P) = 1 (due to Easterman, van der Corput, and possibly others independently)
we get f (x) = x2/3 .
Audience: Can replace P with any h-basis and still have f (x) = x1−1/h .
Note that Erdős proved the existence of A with A(n) ∼ log n and A + P ∼ N, so the primes are not atypical basis.
Audience: Can x2/3 be improved assuming the Goldbach conjecture? Answer: Goldbach gives only
σ(4P) = 1, so no.

2009.4.3. Mel Nathanson. Clarifying earlier problem. We say that two points in Rn are congruent if theirdifference is in Zn . Suppose that k ⊆ Rn is compact and for each x ∈ R there is a y ∈ K such that x ≡ y.
Theorem: A := (K − K) ∩ Zn is a finite set and generates the additive group Zn .
For n = 1, there is a K that will give any set of generators that contains 0 and is symmetric about 0.
For n = 2, which sets of generators arise in this fashion? Specifically, is there a K (compact and hitting

COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

9every residue class modulo 1) such that A ⊆ {(x, y) : xy = 0}? Even more specifically, is there a K with
A = {(0, 0), (±1, 0), (0, ±1)}?
Note since the end of the conference: Renling Jin has solved this problem. Independently, and bydifferent methods, Mario Szegedy has obtained a partial solution.
2009.5. Speakers and Participants Lists.
2009.5.1. Speakers.
• Hoi H. Nguyen <hoi@math.rutgers.edu>• Mariah E. Hamel <mhamel@math.uga.edu>• Steven J. Miller <Steven.J.Miller@williams.edu>• Alex Iosevich <iosevich@gmail.com>• Benjamin Weiss <blweiss@umich.edu>• Brooke Orosz <borosz@gc.cuny.edu>• Charles Helou <cxh22@psu.edu>• Craig Spencer <craigvspencer@gmail.com>• Gang Yu <yu@math.kent.edu>• Jaewoo Lee <jlee1729@hotmail.com>• Jonathan Sondow <jsondow@alumni.princeton.edu>• Julia Wolf <julia.wolf@cantab.net>• Kent Boklan <boklan@boole.cs.qc.edu>• Kevin O’Bryant <obryant@gmail.com>• Lan Nguyen <ltng@umich.edu>• Le Thai Hoang <leth@math.ucla.edu>• Li Guo <liguo@andromeda.rutgers.edu>• Mario Szegedy <szegedy@cs.rutgers.edu>• Mei-Chu Chang <changmeichu03@gmail.com>• Mel Nathanson <melvyn.nathanson@lehman.cuny.edu>• Mohamed El Bachraoui <MElbachraoui@uaeu.ac.ae>• Neil Lyall <lyall@math.uga.edu>• Peter Hegarty <hegarty@chalmers.se>• Renling Jin <jinr@cofc.edu>• Rishi Nath <rnath@york.cuny.edu>• Simon Griffiths <sg332@cam.ac.uk>• Urban Larsson <urban.larsson@yahoo.se>
2009.5.2. Participants.
Adon Amira, New York
Bela Bajnok, Gettysburg College
Kent Boklan, Queens College (CUNY)
Richard T. Bumby, Rutgers University - New Brunswick
Mei-Chu Chang, University of California-Riverside
David Chudnovsky, Polynechnic University - NYU
Bianca De Souza, CUNY Graduate Center
Mohamed El Bachraoui, United Arab Emirates University
Simon Griffiths, University of Montreal
Li Guo, Rutgers University-Newark
Mariah Hamel, University of Georgia
Piper Harris, Princeton University

10

MILLER

Derrick Hart, Rutgers University - New Brunswick
Tanya Haxhoviq, CUNY Graduate CenterPeter Hegarty, Chalmers University of Technology and University of Gothenburg
Charles Helou, Penn State Brandywine
Le Thai Hoang, UCLA
Alex Iosevich, University of Missouri
Renling Jin, College of Charleston
Nathan Kaplan, Harvard University
Walter O. Kravec, Stevens Institute of Technology
Shanta Laishram, University of Waterloo
Urban Larsson, Chalmers University of Technology and University of Gothenburg
Jaewoo Lee, Borough of Manhattan Community College (CUNY)
Ines Legatheaux Martins
Karl Levy, CUNY Graduate Center
Neil Lyall, University of Georgia
Steven J. Miller, Williams College
Rishi Nath, York College (CUNY)Mel Nathanson, Lehman College (CUNY)David Newman, New YorkHoi H. Nguyen, Rutgers University-New Brunswick
Lan Nguyen, University of Michigan
Kevin O’Bryant, College of Staten Island (CUNY)
Brooke Orosz, Essex County College
Gina-Louise Santamaria, Montclair State University
Steven Senger, University of Missouri - Columbia
Satyanand Singh, CUNY Graduate Center
Jonathan Sondow, New York
Craig Spencer, Institute for Advanced Study
Jacob Steinhardt
Mario Szegedy, Rutgers University-New Brunswick
Jonathan Wang
Benjamin Weiss, University of Michigan
Julia Wolf, Rutgers University-New Brunswick
Thomas Wright, Johns Hopkins University
Gang Yu, Kent State University

COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

112010. CANT P ROBLEM S ESSION : 20102010.1. Problem Session III: Friday, May 28th (Chair).
2010.1.1. Nathanson: Classical Problems in Additive Number Theory. N. G. de Bruijn had two papers:(1) On bases for the set of integers, 1949.
(2) On number systems, 1956.
Very few references to these papers. The second paper: he stated and solved a problem; in the first hestated a problem but neither he nor others could solve. Lately, however, these have become of interest to
people in harmonic analysis.
These are related to the idea of complementing sets. Given a finite set A, can you find an infinite set B
such that A ⊕ B = Z? De Bruijn considered a slightly different problem, but in the same spirit. Givena family of sets {Ai }i∈I with I = N or {1, . . . , n}, we are interested
P in sets with the property that N0 =⊕i∈I Ai ; in other words, every non-negative integer is of the form i∈I ai and ai 6= 0 only finitely often. De
Bruijn calls this a British number system. Years ago 12 pence in a shilling, .... The British number system(pence, shillings, pounds) is the motivation for notation. If you have 835 pence that is 3 pounds, 9 shillings
and 7 pence. The British number system is based on 12 and 20.
Using 12 pence is 1 shilling and 20 shillings is 1 pound. Take {gi }i∈I , gi ≥ 2, G0 − 1, G1 = g1 ,G2 = g1 g2 , Gi = g1 g2 · · · gn ,An = Gn−1 ∗ [0, 1, 2, . . . , gi−1 ) = Gi−1 ∗ [0, gi ),
and
A1
A2
A3
An+1

=
=
=
=

{0, 1, 2, . . . , g1−1 }G1 ∗ {0, 1, . . . , g2−1 }G2 ∗ {0, 1, 2, . . . , g3−1 }Gn ∗ N0 ,whered ∗ A = {da : a ∈ A}.

P
Are there other sets? Yes. Let {Ai }i∈I and I = ∪j∈J Ii with Ij ∩ Ij ′ = ∅ for j 6= j ′ , Bj = i∈Ij Ai ,{Bj }j∈J . Comes down to choosing sequence of g’s to be prime numbers to get indecomposable sequence.
Consider a set B of integers such that every n ∈ Z has a unique representation in the form
X
n =
ǫb b
b∈B

where ǫb ∈ {0, 1} and ǫb = 1 finitely often. Let Ai = {0, bi }, ⊕∞i=1 Ai = Z.
Take set of powers of 2: {2i }∞
:
get
all
non-negative
integers.
Suppose we look at {ǫi 2i }∞i=0
i=0 whereǫi ∈ {±1}. Need infinitely many +1s and −1s to be a basis. No other condition necessary. Works if there
are infinitely many +1s and infinitely many −1s. What infinite sets B have this property? Want subset sums
to give each integer once and only once. First thing can say is that we better not have everything even, so
must have at least one odd integer in the set. Then de Bruijn proves something clever: not only at least one
odd integer, but at most one odd integer. Was a conjecture of someone else, de Bruijn proves this conjecture.
Think about this for a minute. Exactly one odd number. If you are going to represent an even number itcannot have that odd number, and thus if divide all even numbers by 2 get another system of this form, so
one of these and only one of these is divisible by 2 and not 4. By induction, see for every power of 2 there
is one and only one number x in this set such that 27 ||x. We can thus write bi = dn 2i with di odd. So B
comes from a sequence of odd numbers. Let’s call this sequence of odd numbers {di }∞i=1 okay; sequenceof odd numbers. In other words, it is an additive basis. Just restated the problem – what sequences of odd
integers are okay?

12

MILLER

No one knows what sequences of odd numbers are okay. De Bruijn proved the following: suppose{d1 , d2 , d3 , . . . } is an okay sequence; this is an okay sequence if and only if {d2 , d3 , d4 , . . . } is okay. Can
throw off any bunch – do again. Can really screw around with an okay sequence – can chop at any point,
any finite sequence of garbage in the beginning. This is an interesting problem. I went this morning to
MathSciNet to see what papers have referenced this paper of de Bruijn. There was a gap of about 50 years,
but now relevant for something in harmonic analysis (they can’t solve this problem, but it is in the same
spirit as something they are interested in).
2010.1.2. Schnirelman. When did additive number theory start? In 1930s Schnirelman proved that every
even number is the sum of a large number of primes; he did this by proving a theorem about sumsets. Before
this the results were beautiful (Fermat, Lagrange, Gauss, Hardy, Ramanujan, Littlewood, Vinogradov);
Schnirelman had a general theorem about integers.Let
A + B = {a + b : a ∈ A, b ∈ B}.
Counting function
A(n) =

X

1.

a∈A
1≤a≤n

Let’s say 0 ∈ A ∩ B to be safe. Defining
δ(A) = inf

A(n)
.
n

Schnirelman provedδ(A + B) ≥ δ(A) + δ(B) − δ(A)δ(B).
Norwegians are funny – go off to the mountains and come down with a great theorem. In WWI de Bruijn
goes up to mountains and invents a sieve method that allows him to prove things about Goldbach and Twin
Primes. No one could understand the paper. Landau couldn’t understand it, didn’t try. Schnirelman did
understand and used it to get his results, which made the result / method fashionable. Now people studied
de Bruijn’s paper. Landau’s exposition in one of the seminal journals became the standard exposition for thede Bruijn sieve. Same thing happened with Selberg. WWII started, he was captured by Germans, released
if promised not to stay in Oslo, went to family home and proved results on zeros of ζ(s).
Could also look atA(n).
δL (A) = limn→∞ n
Say A ∼ B if there is an N such that for all n ≥ N we have n ∈ A if and only if n ∈ B. Embarrassment:
if every element is even then all sums even, must be careful. If δL (hA) > 0 for some h then if d = gcd(A)and 0 ∈ A there there is an h0 such that h0 A ∼ d ∗ N0 . First time appears is in a paper with John C. M.
Nash (the son).
Let 0 ∈ A and dL (hA) = 0 for all h ≥ 1. Assume
A ⊆ 2A ⊆ 3A ⊆ 4A ⊆ · · · ⊆ hA ⊆ · · · .
If any set has positive density then get all integers from some point onward. Maybe in this case some infinite
case appears. The question is: take a set of non-negative integers containing 0 such that all of these sets
have asymptotic density zero. Get an increasing sequence. As add to itself more and more times, does any
structure appear? Can you say something that interests your friends mathematically about this? Is there
anything that must happen?

COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

13

2010.1.3. Alex Kontorovich. Not convinced problem is difficult, but we haven’t made progress. The question is the additive energy in SL(2, Z). This means that we take elements γ1 , γ2 , γ3 , γ4 in SL(2, Z) in a ballBN and want to know how many there are such that γ1 + γ2 = γ3 + γ4 }. The number of points in a ball (4variables, 1 quadratic equation) gives cN 2 .
We have 16 variables (unknowns), 4 quadratic equations (the determinants equaling 1) and 4 linear equations. Want an upper bound of the form ≪ N 4+ǫ . Have a trivial lower bound of N 4 . Easy thing to prove is
N 5 for the following reason. Let(
N2
if ω = 0
η(ω) = #{γ1 γ2 ∈ BN (SL2 ) : γ1 − γ2 = ω} =1+ǫN
if ω 6= 0.
What about non-trivial bounds? See
http://arxiv.org/pdf/1310.7190v1.pdf
for more on this problem.
2010.1.4. Peter Hegarty. This is a problem on Phase Transitions inspired by Hannah Alpert’s talk. Let G
be an Abelian group, A a set of generators, everything infinite. Have S(1), S(2), S(3), . . . , S(r), . . . ,where the sequence is ∞, ∞, . . . , ∞, (n), 0, 0, . . . (where we may or may not have the n term). We shouldbe able to compare the sizes of infinite, i.e., their measure. Suppose G is a compact Abelian group, such as
the circle, and let A be a measurable set. Want to look at Lebesgue (or Haar) measure of the sets: µ(S(1)),µ(S(2)), et cetera. The sequence should be unimodal (regular).
David Neumann looked at something similar. For finite groups looking at the sizes, did a lot of computations with different groups and generating sets. Did find an example where it wasn’t the case, but typicallydo have unimodality. Hegarty conjectured that for any finite group (not necessarily Abelian) can always finda set of generators such that the sequence is unimodal.
2010.2. Problem Session IV: Saturday, May 29th.
2010.2.1. Peter Hegarty. Let A ⊂ N,r(A, n) = #{(a1 , a2 ) : a1 + a2 = n}.
What sequences of non-negative integers can be asymptotic representation functions? Of course there are
restrictions if start from 0. Obviously only one way to represent 0 (0+0). Given a sequence of numbers,
want the sequence to equal r(A, n) starting at some point. Assuming Erdös-Turan, cannot be bounded andsimultaneously not have infinitely many zeros.
Comment from Nathanson: Matter of choice whether take r(A, n) or the functionr(A, n) = #{(a1 , a2 ) : a1 + a2 = n, a1 ≤ a2 }.

More generally, say |S| = ∞ and S ⊆ G, A is an asymptotic basis (of order 2) for S if S ⊂∼ A + A (up to
finite sets). Let
rA (s) = #{(a1 , a2 ) : a1 + a2 = s}.
We have rA : S → N ∪ {∞}. Hardest problem is what we had earlier.
2010.2.2. Mel Nathanson. Erdös-Renyi Method: LetΩ = {all sequences of non − negative integers}.
Let 0 ≤ p(n) ≤ 1 for n = 0, 1, 2, . . . . Then there exists a probability measure Pr on Ω such that
Pn (En ) := Pn ({A ∈ Ω : n ∈ A}) = p(n)then the events En are independent.

14

MILLERβ

If choose p(n) to be something like a logarithm over a power of n, say α lognγ n with 1/3 < γ ≤ 1/2 –want a result that doesn’t use any probability. If put this probability measure on the sequence of integers,then if A ⊂ N0 with A + A ∼ N0 and S(n) = {a ∈ A : n − a ∈ A}, then for m 6= n we have2
|S(m) ∩ S(n)| ≤3γ − 1for all but finitely many pairs of integers.
Below is an example of where this result was used. An asymptotic basis means every number from somepoint onward can be written as a + a′ with a, a′ ∈ A. An asymptotic basis A is minimal if no proper subsetof A is an asymptotic basis. This means we have the set of integers with the property that if throw away
any number then all of a sudden infinitely many numbers cannot be represented. Came up in an attempt toconstruct a counter-example to the Erdös-Turan conjecture. Not every asymptotic basis contains a minimalbasis. There is a theorem that says that if rA (n) → ∞ and |SA (m) ∩ SA (n)| = O(1) then A contains aminimal asymptotic basis.
Theorem: If have a sequence with rA (n) > c log n for some c > 1/ log(4/3) ≈ 3.47606 and n ≥ n0
then A contains a minimal asymptotic basis.
2010.3. Speaker List.
• Hannah Alpert, University of Chicago• Paul Baginski, Universite Claude Bernard Lyon, France• Gautami Bhowmik, Universite Lille, France• Kent Boklan, Queens College (CUNY)• Mei-Chu Chang, University of California-Riverside• Scott Chapman, Sam Houston State University• Brian Cook, University of British Columbia• David Covert, University of Missouri• Aviezri Fraenkel, Weizmann Institute of Science, Israel• John Friedlander, University of Toronto• John Griesmer, University of British Columbia• Sinan Gunturk, Courant Institute, NYU• Peter Hegarty, Chalmers University of Technology and University of Gothenburg• Charles Helou, Penn State Brandywine• Alex Iosevich, University of Missouri• Renling Jin, College of Charleston• William J. Keith, Drexel University• Alex Kontorovich, Institute for Advanced Study• Brandt Kronholm, SUNY at Albany• Urban Larsson, Chalmers University of Technology and University of Gothenburg• Jaewoo Lee, Borough of Manhattan Community College (CUNY)• Zeljka Ljujic, CUNY Graduate Center• Neil Lyall, University of Georgia• Steven J. Miller, Williams College• Rishi Nath, York College (CUNY)• Mel Nathanson, Lehman College (CUNY)• Lan Nguyen, University of Michigan• Kevin O’Bryant, College of Staten Island (CUNY)• Alex Rice, University of Georgia• Steven Senger, University of Missouri• Jonathan Sondow, New York• John Steinberger, Institute for Theoretical Computer Science, Tsinghua University

COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

15

2011. CANT P ROBLEM S ESSION : 20112011.1. Problem Sessions. There was an issue with my computer and the original file was lost for 2011;
the items below are restored from earlier copies, though I have lost who spoke on what day and thus haverun this as one entry.
2011.1.1. Seva Lev. Problem: Let A ⊂ Fn2 , p ∈ F2 [xj ]nj=1 , and for all a, b ∈ A if a 6= b then p(a + b) = 0.
Does this imply that p(0) = 0?
For example, if A = {a, b} then p(a + b) = 0 does not imply p(0) = 0.
If A is large and the degree of p is small, what is true? For a given p, how large must |A| be for this to betrue? We have the following:
deg P
0
1
2
3
≤ (f rac12o(1)) nneed|A| ≥ 2
|A| ≥ 3
|A| ≥ n + 3|A| ≥ 2n???.

2011.1.2. Giorgis Petridis. P-R: D2 ≥ 1 implies that there exists v0 vertex disjointed paths of length 2 in G.
Problem: What can be said when D2 ≥ k ∈ Z?
Guess: there exist v0 vertex disjoint trees in G each having at least ki vertices in Vi . Note: there is an
example which shows that one cannot hope to prove this guess using max flow - min out. Guess confirmed
in k = |V0 | = 2 by Petridis.
2011.1.3. Mel Nathanson. Believe the following is an unsolved problem by Hamidoune (he proposed it andno one has solved it):
Problem: Let G be a torsion free group, G 6= {e}. Let S be a finite subset of G, e ∈ S,
κk (S) = min {|XS| − |X| : finitesets X ⊂ G, |X| ≥ k} .

Hamidoune conjectured that there is an A ⊂ G with |AS| − |A| = κk (S) and |A| = k.
True for k = 1, unknown for k ≥ 2. It is true for ordered groups. As every free abelian group of finite
rank can be ordered, true here. In general for k = 2 still unknown.
2011.1.4. Matthew DeVos. Problem: Let G be a multiplicative group, S ⊂ G a finite set, and set
Π(S) = {s1 · · · sk : si ∈ S, si = sj ⇐⇒ i = j} ∪ {1}.

Not allowed to use an element multiple times. Conjecture: there is a c > 0 such that for every group G and
set S ⊂ G there exists H ⊂ G with |Π(S)| ≥ |H| + c|H| · |S \ H|2 .
True with c = 1/64 when G is abelian.
2011.1.5. David Newman. Problem: How many partitions are there where no frequency is used more thanonce?
For example, the partitions of 4 are {4}, {3, 1}, {2, 2}, {2, 1, 1} and {1, 1, 1, 1}. The ones that are okay
are all but {3, 1}. The problem here is that the two decompositions each occur just once: we have one 3 andone 1.

16

MILLER

2011.1.6. Steven J. Miller, Sean Pegado, Luc Robinson. Problem: For each positive integer k, consider all
A such that |kA + kA| > |kA − kA| and 1 ∈ A (for normalization purposes). Let Ck be the smallest of thelargest elements of such A’s. What can you say about the growth of Ck ?
C1 = 15, C2 = 31, . . . .
2011.1.7. Speaker unremembered. Problem: Assume that you have A, B in a general group and |AB| <α|A| and |AbB| ≤ α|A| for all b ∈ B. Does there exist an absolute c such that X ⊂ A then |XB h | ≤αch |X|?
Rusza showed that if you have |A+Bj | ≤ αj |A| for j = 1, 2, then there is an X such that |X+B1 +B2 | ≤α1 α2 |X|.
Problem: Is there a prescription for X given that Rusza’s theorem shows the existence of X.
2011.1.8. Speaker unremembered. Problem: Let B be a partition of n. Consider the partition where c1 +· · · + ck = n, and 1d1 2d2 · · · ndn . The di ’s are the number of the cj ’s and d1 + · · · + dn = m. Consider



X 
n
n+m+1
1
.
m+n+1
c1 , . . . , ck
n + 1, d1 , . . . , dn
B∈P(n)

What can be said?
Try putting in an r n and summing over n. Maybe this is a holomorphic part of a non-holomorphic Maassform.
2011.1.9. Peter Hegarty. Problem: Consider the least residue of n modulo q, denoted [n]q , which is in{−q/2, . . . , q/2}. Want a function from π : {1, . . . , 27} to itself (a permutation, so 1-1) with the property
that given any a, b, c not all equal with |[a + c − 2b]27 | ≤ 1 then |[π(a) + π(c) − 2π(b)]27 | ≥ 2.
Motivation: replace 27 with n, ..., have a permutation avoiding a progression. Conjecture that a permutation of Zn exists for every n sufficiently large.
2011.1.10. Speaker unremembered. Problem: Define h : {1, . . . , N } → Z/N Z; call it a partial homomorphism if it a bijection such that whenever a, b, ab ∈ {1, . . . , N } then h(ab) = h(a) + h(b) mod N . Does
such a function exist for all N ?
Have built by hand for all N up to 64?
2011.1.11. Steven Senger. The basic idea is that an additive shift will destroy multiplicative structure. Givena large, finite set, A ⊂ N, suppose that |AA| = n. We know that there exists no generalized geometric progression, G, of length c1 n, such that |(AA + 1) ∩ G| ≥ c2 n, where c1 and c2 do not depend on n. The
question is, given the same conditions on A, do there exist sets E, F ⊂ N, such that the following hold for
c3 , c4 independent of n, and δ > 0:
• |E|, |F | ≥ nδ
• |EF | = c3 n
• |(AA + 1) ∩ EF | ≥ c4 n

Even partial results would be interesting to me. Also, considering the problem over R would be interesting
to me.

COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

17

2011.1.12. Urban Larsson. 2 pile Nim can be described as the set of moves on a chessboard made by arook, moving only down and left. Players take turns moving the rook, and the person to move it to thelower-left corner is the winner. The set of legal moves is defined to be{(0, x), (x, 0)}.

In this case, the positions which guarantee victory following perfect play, or p-positions are along the diagonal. That is, the player who consistently moves the rook to the diagonal will eventually win.
In Wythoff Nim, the piece is replaced by a queen, and the diagonal move is added. The set of legal moves
for Wythoff Nim is{(0, x), (x, 0), (x, x)}.
This game has p-positions close to the lines of slope φ and φ−1 , where, φ denotes the golden ratio. For
example, the points (⌊φx⌋, ⌊φ2 x⌋) are p-positions in Wythoff Nim.
Now, adjoin the multiples of the last possible p-positions from Wythoff Nim which are not in Wythoff
Nim, namely the multiples of the knight’s move. The legal moves of the new game are{0, x), (x, 0), (x, x), (x, 2x), (2x, x)}.

The p-positions for this game appear to split along lines of slopes nearly 2.25 and 1.43. Why?
2011.1.13. Thomas Chartier. Let n, k ∈ N, and p = nk + 1 be prime. Exclude 1 and 2. Fixing n does
there exist a k such that
1k , 2k , 3k , . . . , nk
are distinct mod p? The conjecture is that such a k exists for every non-trivial n.
2011.1.14. Mel Nathanson. Recall the classical sum-product problem of Erdős. Given a large set of positive
integers, A ⊂ N, either the set of sums or the set of products should be large. The conjecture is that, forsuch an A, with c independent of n, for any ǫ > 0,max{|A + A|, |AA|} ≥ cn2−ǫ .
2011.2. Speaker List.
(1) Paul Baginski, Universite Claude Bernard Lyon, France(2) Mei-Chu Chang, University of California-Riverside(3) Scott Chapman, Sam Houston State University(4) Jonathan Cutler, Montclair State University(5) Matthew DeVos, Simon Fraser University(6) Aviezri Fraenkel, Weizmann Institute of Science, Israel(7) Peter Hegarty, University of Gothenburg, Sweden(8) Charles Helou, Penn State Brandywine(9) Jerry Hu, University of Houston - Victoria(10) Alex Iosevich, University of Missouri(11) Renling Jin, College of Charleston(12) Nathan Kaplan, Harvard University(13) Mizan R. Khan, Eastern Connecticut State University(14) Omar Kihel, Brock University, Canada(15) Alex Kontorovich, SUNY at Stony Brook(16) Urban Larsson, University of Gothemburg, Sweden(17) Thai Hoang Le, Institute for Advanced Study(18) Vsevolod Lev, University of Haifa, Israel(19) Zeljka Ljujic, CUNY Graduate Center(20) Neil Lyall, University of Georgia(21) Steven J. Miller, Williams College(22) Rishi Nath, York College (CUNY)

18

MILLER(23) Mel Nathanson, Lehman College (CUNY)(24) Hoi H. Nguyen, University of Pennsylvania(25) Lan Nguyen(26) Sean Pegado, Williams College(27) Giorgis Petridis, University of Cambridge(28) Luc Robinson, WIlliams College(29) Steve Senger, University of Missouri(30) Jonathan Sondow, New YorkCOMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

192012. CANT P ROBLEM S ESSION : 20122012.1. Problem Session I: Tuesday, May 22nd (Chair Renling Jin).
• From Renling Jin, jinr@cofc.edu: Define a subset of the natural numbers B to be an essential
component if for all A ⊂ N, σ(A + B) > σ(A) if 0 < σ(A) < 1. B is an extraordinary componentifσ(A + B)= ∞.
lim infσ(A)σ(A)→0
Here
A(x)
.
x≥1 x

σ(A) = inf

Ruzsa conjectured that every essential component is an extraordinary component.
What are the essential components we know? If
B = {k 2 : k ∈ N}
thenσ(A + B) ≥ σ(A)1−1/4
since B is a basis of order four. We getσ(A + B)
1
.
≥ p
4
σ(A)
σ(A)

Similar for cubes or k-powers.
• From Steven J. Miller, sjm1@williams.edu: We say a set A is a More Sums Than Differences Set,or an MSTD set, if |A + A| > |A − A|, where
A+A
A−A

=
=

{ai + aj : ai , aj ∈ A}
{ai − aj : ai , aj ∈ A}.

As addition is commutative and subtraction is not, it’s expected that ‘most’ sets are difference dominated; however, Martin and O’Bryant proved that a positive percentage of sets are sum-dominated.
There are explicit constructions of infinite families of sum-dominant sets. Initially the best result
was a density of nc 2n/2 /2n , then 1/n4 (or 1/n2 ), and now the record is 1/n (where our sets A arechosen uniformly from subsets of {0, 1, . . . , n − 1}). Can you find an ‘explicit’ family that is apositive percentage.
• From Urban Larsson, urban.larsson@yahoo.se: Let A = {0, 1, 3, 4, . . . } for a set that avoids arithmetic progression, thought to be best set to avoid arithmetic progression but not (comes from agreedy construction). Equivalence with a base 3 construction: A = {0, 1, 10, 11, 100, 101, . . . }gives A((3n + 1)/2) = 2n , where A(n) = #{i ∈ A | i < n}. Hence, for all n, A(n) <Cnlog 2/ log 3 ≈ n2/3 . Study impartial heap games. Is it possible to find a game such that the P and
N-positions correspond to the numbers in this construction? (A position is in N if and only if thefirst player wins.) In some sense such that:P P N P P N N
0 1 2 3 4 5 6We rather use three heaps of sizes in three-term arithmetic progression. A legal move is to erase thelargest pile and then to announce one of the smaller piles as the new largest pile. Notation (x, y),where x is the number of tokens in the smallest heap and y in the second smallest. In the tablebelow, the first entry is the outcome, the second is the position, the third is the Grundy value, and20

MILLER

the fourth are the options.
P
N
P
N
N
N
P
N
N
N

(0, 1)(0, 2)(0, 3)(0, 4)(1, 2)(1, 3)(1, 4)(2, 3)(2, 4)(3, 4)

0
1
0
0
1
0
0
2
3
0

(0, 1)(1, 2)(0, 2), (2, 3)(0, 1)(1, 2),(0, 2), (2, 3)(0, 1), (1, 2)(1, 2), (0, 2), (2, 3)(1, 2), (0, 2), (2, 3)

The P positions (Grundy value 0) have both lower heap sizes in the set A. The N positions have
Grundy values > 0, defined as the minimal exclusive of the Grundy values of the options. What are
they? Is it possible to extend the game by adjoining moves to obtain limsupA(n)/nlog 2/ log 3 = ∞?
The game generalizes to k-term arithmetic progressions and the Sidon-condition for example.
How do we extend such games? We need a general definition for the family of games. A ruleset
is a set of finite sets of positive integers. From a position consisting of a set S of non-negative
integers, choose one of the numbers s ∈ S and a set M of numbers from the given ruleset. The next
position, which is a set of nonnegative numbers, is {s − m | m ∈ M }, provided maxM ≤ s. We
get a recursive definition of the set A which determines the P-positions for a given M . A position S
is in P if and only if S ⊂ A. That is S is in N iff S ∩ A 6= ∅. In this sense we can abuse notation andregard A as the set of “P-positions”. A game extension of M is M ∪ M ′ , for M ′ a set of finite setsof nonnegative numbers. For our game the set M is M = {{d, 2d} | d > 0}. One first example ofa game extension is M = {{d, 2d} | d > 0} ∪ {{1}}. Question: does the set A become less dense
for this game than for our original AP-avoiding game?
2012.2. Problem Session II: Wednesday, May 23rd (Chair Steven J Miller).
• From Steven J Miller, sjm1@williams.edu: We investigated in
http://arxiv.org/pdf/1109.4700v2.pdf) properties of |A + A| and A + A as A varies
uniformly over all subsets of {0, 1, . . . , n − 1}. How does the behavior change if we change theprobability of choosing various A’s (see for example my work with Peter Hegarty:
http://arxiv.org/pdf/0707.3417v5).
Another related problem is to ‘clean-up’ the formula we have for the variance. This involves
sums of products of Fibonacci numbers – can the answer be simplified?
What about the expected values of 2kA versus kA − kA.
• From Ryan Ronan, ryan.p.ronan@gmail.com: Earlier today I discussed joint work on generalized
Ramanujan primes,
http://arxiv.org/pdf/1108.0475. One natural question is whether or not for each prime
p there is some constant cp such that p is a cp -Ramanujan prime.
Another question is the distribution of c-Ramanujan primes among the primes, in particular thelength of runs of these and non-these. It can take awhile for the limiting behavior of primes to
set in; it’s dangerous to make conjectures based on small sized data sets. Are the calculations
here sufficiently far enough down the number line to have hit the limiting behavior? For a related
question, perhaps the Cramer model is not the right model to use to build predictions, and instead
we should use a modified sieve to construct ‘random primes’. It would be worthwhile to do so andsee what happens / what the predictions are.

COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

21• From Steven Senger, senger@math.udel.edu: Have a subset A of a finite field Fq satisfying for all ǫand δ positive (1) |A| |AA| ≥ q 3/2+ǫ , (2) |AA| ≤ q 1−δ . For all generalized geometric progressions
G with |G| ≈ |AA| we have |(AA + 1) \ G| ≥ q δ . Can reduce the size constraint (1)? Can we
increase the size of |(AA + 1) \ G| ≥ q δ ?
• From Kevin O’Bryant, obryant@gmail.com: How far out can you go {x1 , x2 , x3 , x4 , · · · } such thatthe first four are in the first four quadrant, the first nine in the first nine subdivisions (3 × 3), the first
16 in the first 4 × 4 and so on.... We know this can’t go on forever, violates Schmidt.
The discrepancy of the sequence {xi } is
Disc({xi }di=1 ) = supR#{xi ∈ R}− A(R) .
d

We have Disc({xi }di=1 ) ≥ C logd d . If we spread the points too well, the discrepancy gets very low.
Let me rephrase – I strongly believe that this logarithmic factor will kill this arrangement.

2012.3. Problem Session III: Thursday, May 24th (Chair Alex Iosevich).
• From Jerry Hu, HuJ@uhv.edu:
This problem is related to Nathanson’s talk “The Calkin-Wilf tree and a forest of linear fractionaltransformations” from Tuesday. Recall the form of the Calkin-Wilf tree, where we have:
a
b

ւ
ց
a+b
a
a+b
b
ւ ց
ւ ց
a
2a + ba + b a + 2b.
2a + b a + b
a + 2bb
When a and b are both initialized as 1, each positive rational number appears on the tree exactly
once.
The question is: how can we generalize this? More specifically, do there exist other trees of the
form
z
ւ
L(z)

ց
R(z)

in which every positive rational number appears exactly once? Can we find all, or any, nontrivial
functional pairs L, R such that this condition holds?
• From Nathan Kaplan, nathanckaplan@gmail.com: Here is a problem about counting lines among
points in Fn3 . I will give two different kinds of motivation for why someone might be interested in
this.
The card game SET is played with 81 distinct cards, each of which has four attributes (number,color, shading, and shape), where each attribute has three possibilities. We can identify a card witha 4-tuple (x1 , x2 , x3 , x4 ), where each xi ∈ F3 . The game is played by collecting sets. A set is acollection of three cards (x, y, z) such that for each of the four attributes each card is the same or
all three cards are different. It is equivalent that the vectors in F43 represented by our three cards
take the form (x, y, −(x + y)), or equivalently, (x, x + d, x + 2d). Therefore, we see that what weare looking for is a three term arithmetic progression in Fn3 . In Fn3 a 3-term AP is equivalent to aline. A set of vectors with no 3-term AP is called a cap set. The cap set problem asks, “What is the
maximum size of a cap set in Fn3 ?”. This problem is very hard and has been well-studied. Exact
answers are known only for n ≤ 6. We note that for n = 3 the cap set problem is equivalent toasking for the maximum number of SET cards one can have so that there is no set among them. The

22

MILLER

answer to this is 20 and an argument is given in the paper The Card Game Set by Benjamin Davisand Diane MacLagan.
There is a related problem motivated by SET which does not seem to have appeared in the literature. The game is usually played by dealing out 12 cards. We know that it is possible to haveno sets at all, but we could ask for the largest number of sets which could occur among 12 cards. I
can show that this is 14, but the argument is sort of ad hoc and not so satisfying. I have not foundanything written before about the following question. What is the maximum number of lines thatm points in Fn3 can contain? Note that any two points determine a unique line, so if a set contains
many lines, then it determines few lines. Equivalently we could ask for the minimum number oflines determined by m points in Fn3 . This question is very general and includes the cap set problem
as a subcase. This is because the number of lines contained in a subset of Fn3 determines the number of lines contained in its complement, so if we know the maximum number of lines among any
collection of m points for all m, then we also know the minimum number of lines among m points.
Here is the actual problem I am asking. In the argument for the maximum number of lines among
12 points in F43 is 14, it is clear that the maximum number of lines among 12 points in Fn3 is 14 forany n ≥ 3. That is, if we want lots of lines, the best thing that we can do is to put our points into thesmallest possible dimensional subspace that can contain them.
Conjecture 2012.1. Fix m ≥ 0 and let d = ⌈log3 (m)⌉. For any n ≥ d, the maximum number oflines contained among m points in Fn3 is equal to the maximum number of lines contained amongm points in Fd3 .
I think that this is probably true and that the proof for it is probably easy. One could also ask
similar questions for Fnq for other q.
Here is some extra motivation that the cap set problem is interesting. Tic-Tac-Toe on a 3 × 3 × 3
board can never end in a draw no matter how many moves are made by each player. This is the firstcase of a more general phenomenon, the Hales-Jewett Theorem. Given k, there exists a d such that
Tic-Tac-Toe on a k × · · · k = [k]n board (where it takes k in a row to win) cannot end in a draw
no matter how many times each player moves. A more precise statement is that for large enoughn, either a set or its complement must contain a combinatorial line. I won’t define exactly what a
combinatorial line is, but it is a slightly more restrictive condition than a Tic-Tac-Toe line, which isslightly more restrictive than the type of line described above in the discussion of SET.
A few years ago, the initial Polymath project organized by Tim Gowers was focused on giving a
combinatorial proof of the Density Hales-Jewett Theorem. The only previous proof of this theorem
involved arguments from ergodic theory. Let cn,k be the largest number of points of [k]n which
does not contain a combinatorial line. Let c′n,k be the largest number of points of [k]n which does
not contain a geometric line (you can think of this as a Tic-Tac-Toe line. These are called Moser
numbers. Finally, let c′′n,k be the largest number of points of [k]n without a line of the type describedabove. Clearly c′′n,k ≤ c′n,k ≤ cn,k .
Theorem 2012.2 (Density Hales-Jewett). Fix k ≥ 1. Then
cn,k
lim
= 0.
n→∞ nkThis result is important in understanding the growth of cap sets. The Polymath project also proved
the best known lower bound for cn,k . It is quite difficult to compute these numbers in general, evenfor small k. We mentioned above that c′′4,3 = 20 and it is also known that c′′5,3 = 45 and thatc′′6,3 = 112. This last statement determines the maximum number of lines among 36 − 112 points in[3]6 , for example. The Polymath project also determined more values of cn,3 and c′n,3 than previously
known.
Since so much work has gone into understanding large subsets of [k]n with no lines, it seems
reasonable to study collections of points which contain the largest possible number of lines.

COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

23

2012.4. Problem Session IV: Friday, May 25th (Chair Kevin O’Bryant). The following papers are relevant for the problems proposed by Steven Miller.
• http://arxiv.org/abs/1107.2718• http://arxiv.org/abs/1008.3204• http://arxiv.org/abs/1008.3202 (the gap paper referenced below is in preprint stage,
but available upon request).
• http://www.emis.de/journals/INTEGERS/papers/j57/j57.pdf (Hannah Alpert).
Proposed problems.
• From Steven J. Miller, sjm1@williams.edu: The following problems are related to Zeckendorf decompositions. Many of these are currently being studied by my summer REU students in theWilliams 2012 SMALL program. If you are interested in working on these, please email me at
sjm1@williams.edu.
⋄ We know every number has a unique Zeckendorf decomposition, and appropriately localized
the number of summands converges to being a Gaussian. What happens if we have a decomposition
where some integers have multiple representations? What if there are some integers that have norepresentations? Instead of counting the total number of summands, what if you just count how
many of each summand one has (so in decimal 4031 wouldn’t count as 4+0+3+1 but 1+0+1+1).
⋄ We have formulas for the limiting distribution of gaps between summands of Fibonacci andsome generalized Fibonacci sequences. Try to find formulas for general recurrence relations as afunction of the coefficients of the relations. Do this for the signed Fibonacci decomposition (seeHannah Alpert’s paper; can we generalize signed distributions to other recurrence relations). Whatabout the distribution of the largest gap (that should grow with n for numbers between Hn and
Hn+1 ). If we appropriately normalize it, does it have a nice limiting distribution?
• From Mizan Khan, khanm@easternct.edu: Let
Hn := {(x, y) ∈ Z × Z : xy ≡ 1 (mod n), 1 ≤ x, y ≤ n − 1)}.

Consider the convex closure of Hn – what can we say about the number of vertices in this convex
closure? Let v(n) be the number of vertices. Easily, v(n) ≥ 2(τ (n − 1) − 1), where τ is the numberof positive divisors.
It is easy to see that lim sup v(n) = ∞. Can we show that limn→∞ v(n) = ∞?
Also, consider D(n) = v(n) − 2(τ (n − 1) − 1). We know that D(n) > 0 for a set of density 1
in the naturals and furthermore D(n) = 0 on a set which is ≫ logx x . Can we improve the second
estimate?
• From Steven Senger, senger@math.udel.edu: We will call a family of sets, Pn ⊂ [0, 1]2 , s-adaptable
if they satisfy the following bound:X1|x − y|−s . 1.
n2x6=y;x,y∈Pn

The Szemerédi-Trotter incidence theorem says that for a set of n points and m “reasonable" curvesin the plane, the number of incidences of points and curves is bounded above by2

I . (nm) 3 + n + m.
Can we get better incidence bounds for s-adaptable sets? Specifically, can we get tighter bounds inthe case of n points and n circles centered at those points?
• From Nathan Pflueger, pflueger@math.harvard.edu: Suppose S is a numerical semigroup, S ⊂ N+ ,closed under addition, i.e., S + S ⊂ S. Let G := N+ \ S. Define the weight of S to be w(s) =|{(x, y) ∈ S × G : 0 < x < y}|. Define the irreducible elements of S to be the minimal generators.
Define the effective weight of S to be wef f (s) = |{(x, y) ∈ Sirred × G : 0 < x < y}|. Let thegenus of S be g = |G|.
For example, S = h3, 5i. Then w(s) = 4, and wef f (s) = 3.

24

MILLER

Can we characterize the genus g subgroups of largest effective weight? We believe the largest is2≈ g4 , and in the form ha, a + 1, . . . , b − 1, bi, where b < 2a.
This comes from algebraic geometry. Pick a point p on an algebraic curve or surface. S ={ordp (f ) : f is a rational function}, where ordp (f ) is the order of the single pole at p of f .
2012.5. Speaker List.
• John Bryk, John Jay College (CUNY)• Mei-Chu Chang, University of California-Riverside• Emel Demirel, Bergen County College• Frederic Gilbert, Ecole Polytechnique, Paris• Christopher Hanusa, Queens College (CUNY)• Charles Helou, Penn State Brandywine• Jerry Hu, University of Houston - Victoria• Alex Iosevich, University of Rochester• Geoff Iyer, University of Michigan• Renling Jin, College of Charleston• Nathan Kaplan, Harvard University• Mizan R. Khan, Eastern Connecticut State University• Sandra Kingan, Brooklyn College (CUNY)• Alex Kontorovich, Yale University• Urban Larsson, Chalmers University of Technology and University of Gothenburg• Oleg Lazarev, Princeton University• Xian-Jin Li, Brigham Young University• Neil Lyall, University of Georgia• Steven J. Miller, Williams College• Rishi Nath, York College (CUNY)• Mel Nathanson, Lehman College (CUNY)• Kevin O’Bryant, College of Staten Island (CUNY)• Kerry Ojakian, St. Joseph’s College, New York• Ryan Ronan, Cooper Union• Steven Senger, University of Delaware• Jonathan Sondow, New York• Liyang Zhang, Williams College• Wei Zhang, Columbia University

COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

25

2013. CANT P ROBLEM S ESSION : 20132013.1. Problem Session I: Tuesday, May 21st (Chair Steven Miller).
2013.1.1. MSTD sets and their Generalizations. Proposed by Steven J. Miller and expanded on by theaudience: There are many problems one can ask about More Sums Than Differences sets. Here are just afew.
• We know that, in the uniform model, a positive percentage of the 2n subsets of {0, 1, . . . , n − 1} aresum-dominant. Unfortunately these proofs are non-constructive, in that one shows with high probability almost anything thrown between two specially chosen fringes work. Early constructions of
explicit families often involved tweaking arithmetic progressions (which are balanced). While theseearly families were often sub-exponential in terms of their relative size, work of Miller, Scheinerman
and Orosz proved that one can find ‘explicit’ families with density 1/n2 ; Zhao obtained a density of
1/n through the use of bidirectional ballot sequences. Can one find an explicit formula with a better
density (or, dare to dream, one that is a positive percentage?).

• Continue to investigate phase transitions, and the natural of the relative size function, for more summands with different combinations of size. This is currently being studied by students in Miller’s
2013 REU at Williams.

• Instead of looking at A + A and A − A, choose A and B randomly and study A + B and A − B (ofcourse, A − B allow both a − b and b − a for a ∈ A and b ∈ B.
• In determining if A is sum-dominant or difference-dominant, it doesn’t matter how much larger one
is than the other. Try and find a natural weighting on the sets, try to take into account by how muchone beats the other.

• Is there a set A such that |A + A| > |A − A| and |A · A| > |A/A|? If yes, can you find an
explicit, infinite family? What is the density of such sets? Note: Miller finds this problem interesting and wants to bring this to his REU students. Anyone interested in collaborating please email
sjm1@williams.edu.
• Instead of looking at subsets of the integers or finite groups, look at subsets of Zd , intersected withdifferent regions (say spheres, boxes). These sets have different fringe structures. How does theshape of the fringe affect the answer? We can play with the relative sizes of the length and width ofa box in two dimensions, for example. This is currently being studied by students in Miller’s 2013
REU at Williams.

• Can we say anything about MSTD sets in the continuous case? Is this related to some results on
measures? What about subsets of fractals or other special objects (similar to the modular hyperbolas
Amanda mentioned).

• (Mizan Khan): Speaking of Amanda’s talk, the 84% lower bound mentioned is almost surely not
the true answer. What do numerical investigations suggest? What is the correct limiting behavior?

26

MILLER

2013.1.2. Weakened Convex Functions. Problem proposed by Seva Lev.

Consider functions f : [0, 1] → R that satisfy (1) max{f (0), f (1)} ≤ 0 and (2) for any 0 ≤ x1 ≤ · · · ≤xm ≤ 1 we have
x1 + · · · + xm
f (x1 ) + · · · + f (xm )f≤+ (xm − x1 ).
mm
Note that convex functions satisfy this.
Set
Fm (x) = sup{f (x) : f ∈ Fm },where Fm ∈ C([0, 1]) and F (0) = F (1) = 0 < F (x) for 0 < x < 1. What is Fm explicitly?
Results are known for m ∈ {2, 3, 4}. For such m we have
Fm (x) =∞X

m−k min{||mk−1 x||, 1/m}.

k=1When m = 2 we have 2ω(x), whereω(x) =∞
X
k=0

2−k ||2k x||.

What about m = 4?
2013.2. Problem Session II: Wednesday, May 23rd (Chair Seva Lev).
2013.2.1. Matrices and Curves. Problem proposed by Seva Lev.
Consider an m × n matrix A whose entries are 0 or 1. Consider n points in the plane {p1 , . . . , pn }, witheach point corresponding to a column of A. If there exists m curves (continuous, no self-intersection){c1 , . . . , cm } with each curve corresponding to a column of A, such that• curve ci passes through point pj if Ai,j = 1 and does not pass through point pj if Ai,j = 0, and• any two curves intersect at most once,

we will call A realizable by curves.

The following are questions we can ask:
• What conditions can we put on A to guarantee A is realizable? Note: requiring the dot product ofany two rows of A to be at most one does not guarantee A is realizable.
• Can you find a small matrix that is not realizable?
• Lastly, if A is realizable, does this mean AT is realizable? The speaker does not see a reason thisshould be true, but hasn’t found a counterexample yet.
This problem might be related to planar graphs.
2013.2.2. Enumerating Points in the Plane with Polynomials. Problem proposed by Mel Nathanson.
Consider the set P = {(x, y) : x ≥ 0, 0 ≤ y ≤ αx}. Does there exist a bijective polynomial
f : P → N ∪ {0}?
For instance, if α = 1, then f (x, y) = x(x+1)+ y. Notice when y = 0, f (x, 0) is a triangular number.
2
However, even when α = 2/3, it is not clear what f should be or if f even exists.

COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

27

2013.2.3. Sumsets. Problem posed by Dmitry Zhelezov.
Let B be a set such that |B| = n. Let
B + B ⊇ A = {a0 < · · · < an },where A is concave (a1 −a0 > a2 −a1 > · · · > an −an−1 ) or convex (a1 −a0 < a2 −a1 < · · · < an −an−1 ).
Is it true that |A| = O(n2 )?
Problem posed by Steven Senger.
Let A and B be “large” subsets of N (or R, or Z, . . . ). Do there exists “large” subsets of N, C and D,
such that |((A · B) + 1) ∩ (C · D)| = |A · B|1−ǫ ?
2013.3. Problem Session III: Thursday, May 24th (Chair Kevin O’Bryant).
2013.3.1. 3-term Geometric Progressions in Sets of Positive Density. Problem proposed by Kevin O’Bryant.

As motivation for this problem, recall Van der Waerden’s Theorem: given any partition of N, at least
one part has an arithmetic progression of arbitrarily large length. Similarly, we have Szemeredi’s Theorem:
given any set of positive density in N, there exists an arithmetic progression of arbitrarily large length. Here
we are defining the density of A ⊆ N as d(A) = limn→∞ |A∩[1,n)|.
n
It is known that Van der Waerden’s Theorem holds for geometric progressions as well. We would like toconsider Szemeredi’s Theorem for geometric progressions, but unfortunately it is not true: the square-free
integers provide a simple counter-example. Currently, there is work being done on which densities we canobtain with no geometric progressions.
The original problem proposed in the session was: if A ⊆ N has density 1, does A have a three-term
geometric progression? After some Googling by Nathan Kaplan, a 1996 paper by Brienne Brown and Daniel
M. Gordon, “On Sequences Without Geometric Progressions”, was found which stated that if A ⊆ N has adensity and has no 3-term geometric progressions, then the density of A is bounded by .869.
The revised problem proposed is: Given a subset A ⊆ N, which densities of A guarantee 3-term geometricprogressions?
2013.3.2. Convex Subsets of Sumsets. Problem proposed by Dmitry Zhelezov and requested by Giorgis
Petridis.

We consider a variant of the Erdös-Newman conjecture, but replace the idea of squaring a set with sumsets.
The problem proposed is: does there exist any set B with |B| = n such that B + B ⊇ A for some convex
set A with |A| = Ω(n2 )?
2013.4. Problem Session IV: Friday, May 24th (Chair Renling Jin).
2013.4.1. Sumsets. Problem proposed by Renling Jin.

Let A, B ⊆ N such that maxA ≥ maxB, 0 = minA = minB, and gcd(A, B) = 1. Let δ = 1 if
maxA = maxB and 0 otherwise. If |A + B| = |A| + |B| − 2δ, what structure can A + B have? We canalso ask the same question if δ is replaced by δ(A, B), where (A, B) = 1 if A ⊆ B and 0 otherwise.

28

MILLER

2013.5. Additional Problems. Proposed by Vsevolod F. Lev.
For integer m ≥ 2, let Fm denote the class of all real-valued functions f , defined on the interval [0, 1]
and satisfying the boundary condition max{f (0), f (1)} ≤ 0 and the “relaxed convexity” condition
x1 + . . . + xm
f (x1 ) + · · · + f (xm )f≤+ (xm − x1 ),mm

0 ≤ x1 ≤ · · · ≤ xm ≤ 1. Now, let Fm := sup{f : f ∈ Fm }. It is easy to prove that Fm ∈ C[0, 1],
0 = Fm (0) = Fm (1) < Fm (x) for all x ∈ (0, 1), Fm (1 − x) = Fm (x) for all x ∈ [0, 1], and, somewhat
surprisingly, Fm ∈ Fm (meaning that Fm is the maximal function of the class Fm ). What is Fm , explicitly?
We have∞X
Fm (x) =m1−k min{kmk xk, 1/m}, m ∈ {2, 3, 4}
k=0(where kxk denotes the distance from x to the nearest integer), but for m ≥ 5 this fails to hold.

It is easy to see that for any 0-1 matrix, say M , one always can find a system of simple curves and asystem of points in the plane so that their incidence matrix is exactly the matrix M . Suppose now that any
pair of curves is allowed to intersect in at most one point (belonging or not to our system of points), andlet’s say that M is realizable if such curves and points can be found. Clearly, a necessary condition forthis is that the scalar product of any two rows of M be at most 1, but this condition is insufficient: say,for q large enough, by the Trotter-Szemeredi theorem, the point-line incidence matrix of P G(q, 2) has twomany incidences to be realizable. What are other reasonable necessary / sufficient conditions for M to berealizable? What are "small" examples of non-realizable 0-1 matrices?
2013.6. Speaker List.
• Paul Baginski, Smith College• Arnab Bhattacharyya, DIMACS, Rutgers University• Gautami Bhowmik, Universite de Lille, France• Thomas Bloom, University of Bristol, UK• Tomas Boothby, Simon Fraser University, Canada• Amanda Bower, University of Michigan-Dearborn• Jeff Breeding II, Fordham University• Javier Cilleruelo, University of Madrid, Spain• David Covert, University of Missouri - St. Louis• Matthew Devos, Simon Fraser University, Canada• Mauro Di Nasso, University of Pisa, Italy• Mohamed El Bachraoui, United Arab Emirates University, UAE• Leopold Flatto, City College (CUNY) and Bell Labs
• George Grossman, Central Michigan University• Christopher R. H. Hanusa, Queens College (CUNY)• Derrick Hart, Kansas State University• Kevin Henriot, Universite de Montreal• Ginny Hogan, Stanford University• Jerry Hu, University of Houston - Victoria• Renling Jin, Colege of Charleston• Delaram Kahrobaei, New York City Tech (CUNY)• Nathan Kaplan, Harvard University• Omar Kihel, Brock University, Canada

COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15• Sandra Kingan, Brooklyn College (CUNY)• Thai Hoang Le, University of Texas• Seva Lev, University of Haifa, Israel• Neil Lyall, University of Georgia• Richard Magner, Eastern Connecticut State University• Steven J. Miller, Williams College• Rishi Nath, York College (CUNY)• Mel Nathanson, Lehman College (CUNY)• Kevin O’Bryant, College of Staten Island (CUNY)• Brooke Orosz, Essex County College• Giorgis Petridis, University of Rochester• Alex Rice, Bucknell University• Tom Sanders, Oxford University, UK• Steven Senger, University of Delaware• Satyanand Singh, New York Tech (CUNY)• Jonathan Sondow, New York• Dmitry Zhelezov, Chalmers Institute of Technology, Sweden

29

30

MILLER

2014. CANT P ROBLEM S ESSION : 20142014.1. Problem Session I: Wednesday, May 28th (Chair Steven J Miller).
2014.1.1. Steve Senger. From last year from a talk of Dmitry Zhelezov.
Let A ⊂ R, |A| < ∞, let P be the longest arithmetic progression in AA = {ab : a, b ∈ A}. We have
|P | ≤ cn1+ǫ ≪ n2 .
Dmintry (possibly from Hegarty): What if instead of R we have Fq , the finite field with q elements?
Due to Grosu we get the longest progression is at most cn1+ǫ if n ≤ c log log log p where q = p a prime.
Question: What bounds can I get on the size of P if we replace R with Fq ? Here q can be anything.
2014.1.2. Steven J Miller. The following builds on my talk from earlier.
• How does the structure of number affect the answer or the rate of convergence?
• How does the answer depend on c?
• What is the best way to compute all the k-symmetric means for a given n? What if we want just a
certain one (such as k = n/2?).
• Find other sequences and compute these means – is there an interesting phase transition?
2014.1.3. Steven J Miller. Consider the 196 game (or problem). Take an n-digit number; if it is not apalindrome reverse the digits and add. If the sum is not a palindrome continue, else stop. Lather, rinse andrepeat. It’s called the 196 problem as 196 is the first number where we don’t know if the process terminates(in a palindrome) or goes off to infinity. We know numbers that do not terminate in base 2 (as well as powersof 2, base 11, base 17 and base 26).
What can you say about this problem? What about other bases than 10? What about other decomposition
schemes? See http://www.math.niu.edu/~rusin/known-math/96/palindrome.
2014.1.4. Nathan Kaplan. Let C be a cubic curve in P2 (Fq ). Want a large subset so that there are no threepoints on a line.
The set of Fq -points form an abelian group G. Three points sum to zero if and only if they lie on a line.
Given group G what’s the largest subset H s.t. x + y + z = 0 with x, y, z distinct has no solutions in H?
For example takee G = Z/2Z × G′ and take (1, g).
What if G = Z/pZ, consider {0, 1, 2, . . . , ⌊p/3⌋}.
What if Z/5Z × G′ , take things of the form (1, g) and (4, g). For each group ask such a question.
One thing you can do is look at a greedy construction. What is the best percentage you can get?
2014.2. Problem Session II: Thursday, May 29th (Chair Kevin O’Bryant).
2014.2.1. Kevin O’Bryant ? A k-GP cover of [N ] is a family of F of k-term geometric progressions with[
[N ] ⊆
F.
F ∈F

Set

|F|
,
N →∞ F N

γk = lim inf

the infimum being over all k-GP covers of [N ].
It is easy to see that γ3 ≥ γ4 ≥ · · · , and by basic counting γk ≥ 1/k. The covernoF = b · 2ki · {1, 2, . . . , 2k−1 } : 1 ≤ b · 2ki ≤ N, i ≥ 0, b odd
shows that2k,
2(2k − 1)so that limk→∞ γk exists and is in [0, 1/2]. I conjecture that the limit is positive.
γk ≤COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

31

Comment from Bloom (in audience): The GP {1, 2, . . . , 2N −1 } is covered by the APs {1, 2, 3, 4}, {8, 16, 24, 32}, . . . ,so the analog of γk does go to 0.
Comment from Xiaoyu (in audience): Each GP has at most 2 squarefree numbers, so γk ≥ 3/π 2 . This
proves the conjecture, but leaves open the precise limit.
2014.2.2. David Newman. About partitions. FindingQtwo sets of partitions which are equal. Finding a typeof partition which can divide into two different sets. (1 + xn ) counts partition into distinct parts. Change
plus sign into minus signs:
Y(1 − xn ) = 1 − x − x2 + x5 + x7 + · · · .

Most of the time, the partitions (?) are equal, but for 1, 2, 5, 7, ... , they differs by one
Y 1= (1 + x + x2 + · · · )(1 + x2 + x4 + · · · ) · · · .
1 − xn
Question: if you change some of the plus signs on the RHS to minus signs, is is possible to get all thecoefficients (when you expand) to be −1, 0, 1.
“I have an example where it works up to x101 .”Kevin O’Bryant: throw in lots of ǫ (taking value in ±1), becomes a SAT problem.

2014.3. Problem Session III: Friday, May 24th (Chair Mel Nathanson).
a. Right child is a+b
2014.3.1. Mel Nathanson. Think of ab as being a parent of 2 children. Left child is a+bb .
Starting with 1 as root, this gives tree with rows

1

(4)

1/2, 2(5)

1/3, 3/2, 2/3, 3/1(6)

1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4
..
.

(7)
(8)

“Calkin-Wilf tree”
Every fraction occurs exactly once in this tree.
z
Start with z (variable) at root instead of 1. Apply Calkin-Wilf: z 7→ ( z+1, z + 1). Get linear fractionaltransformations. f (z) = az+b
.
cz+d




1 1
1 0
Rule from parent to children: apply matrices
and
0 1
1 1
Depth formula (involving continued fraction) holds in the Calkin-Wilf tree for z.
f (z) = [q0 , q1 , . . . , qk−1 , qk + z] if k is evenf (z) = [q0 , q1 , . . . , qk−1 , qk , z] if k is odd
The form is different for k even/odd. However, if you use that formula above for k even when k is odd,
you get a fractional linear transformation with det −1. (i.e., like starting a tree with 1/z, gives tree with det−1.) For a given determinant, only finitely many orphans (i.e., no parent) of that determinant.
Question from Nathanson: For a given determinant, how many orphans?




1 2
1 0
Question from Harald Helfgott: What if the parent to children rules use the matrices
and
0 1
2 1
instead?
Question from Thao Do: what happens if you start with i instead of 1 as the root? (i.e., let z = i) you gettree with elements of Q[i].
zNathanson: if z = −1, then z 7→ z+1
gives you −1 again... if you’re looking at complex numbers.

32

MILLER

Thomas Bloom: use fields of characteristic p? (Nathanson: “I don’t know anything about char p.”)2014.3.2. Thomas Bloom. You have the sum set, different set, product set, ratio set.
Because of commutativity, you expect difference set to be larger than sum set.
Question: Is there some subset A ⊂ N that is both MSTD and MPTR?
MSTD “more sums than differences”: |A + A| > |A − A|
MPTR “more products than ratios”: as well as |A · A| > |A/A|.
Nathanson: what is the probability measure? We’ve seen MSTD sets before but not the multiplicative.
Note: from an MSTD set, can exponentiate to get an MPTR set.
Comments from Thao Do: in order to have MSTD, must have “almost symmetric form” i.e., smallest +largest = 2nd smallest + 2nd largest = 3rd smallest + 3rd largest, etc. (then change around a little and beclever) a1 + b1 = a2 + b2 implies a1 − b2 = a2 − b1 .
I = {(a1 , b1 ), (a2 , b2 ) : a1 + b1 = a2 + b2 }.
J = {(a1 , b1 0, (a2 , b2 ) : a1 − b1 = a2 − b2 }.
Nathanson: tell Miller to have students working on MSTD/MPTR over summer. Note from Miller:
done!
Bloom: I don’t think these sets exist.

2014.4. Speaker List. Talks here: http://www.theoryofnumbers.com/CANT2014-program.
pdf.
• Sukumar Das Adhikari, Harish-Chandra Research Institute, India• Paul Baginski, Fair?eld University• Thomas Bloom, University of Bristol• Bren Cavallo, CUNY Graduate Center• Alan Chang, Princeton University• Jean-Marc Deshouillers, IPB-IMB Bordeaux, France• Charles Helou, Penn State Brandywine• Nathan Kaplan, Yale University• Sandra Kingan, Brooklyn College (CUNY)• Angel Kumchev, Towson State University• Thai Hoang Le, University of Texas• Eshita Mazumdar, Harish-Chandra Research Institute, Allahabad, India• Nathan McNew, Dartmouth College• Steven J. Miller, Williams College• Mel Nathanson, Lehman College, CUNY
• Lan Nguyen, University of Wisconsin-Parkside• Kevin O’Bryant, College of Staten Island, CUNY
• Alberto Perelli, University of Genova, Italy• Giorgis Petridis, University of Rochester• Luciane Quoos, Instituto de Matemt’atica, UFRJ, Rio de Janeiro, Brasil• Steven Senger, University of Delaware• Satyanand Singh, New York City Tech (CUNY)• Jonathan Sondow, New York• Yonutz V. Stancescu, Afeka College, Tel Aviv, Israel• Tim Susse, CUNY Graduate Center• Johann Thiel, New York City Tech (CUNY)
The abstracts are here: http://www.theoryofnumbers.com/CANT2014-abstracts.pdf.

COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

33

2015. CANT P ROBLEM S ESSION : 2015
2015.1. Phase Transitions in MSTD sets: Steven J Miller. In previous years I talked about phase transitions in the behavior of |A + A| and |A − A| when each element in {0, . . . , N } is chosen independently
with probability p(N ) = N −δ as δ hits 1/2. What happens with three summands? Four?
What happens if we restrict A to special types of sets? How does the additional structure affect theanswer?
Also, is there an ‘explicit’ construction of an infinite family of MSTD sets? The word ‘explicit’ isdeliberately not being defined; I would like some nice, concrete procedure that does not involve randomness.
Finally, is this the 14th or the 13th CANT?
2015.2. An accidental sequence: Satyanand Singh. The two outer graphs which form an envelope aroundγ3 ((6j + 2)5 ) illustrate that:
ln(6j + 2)5ln(6j + 2)55< γ3 ((6j + 2) ) <.
3 ln 3ln 3

The upper bound is easily seen by finding the power of 3 that is closest to (6j + 2)5 but does not exceed
it. We can also say for certain that γ3 ((6j + 2)5 ) ≥ 3, since Bennett dispensed of the two term case in [?]and equality occurs when 25 = 33 + 31 + 2.
 We werenot able to prove the lower bound suggested by theln(6j+2)55experimental results, i.e., γ3 ((6j + 2) ) >for j ≥ 1. This would completely resolve the case
3 ln 3for q = 5.

Problem 1. For both a and b odd, where a > b > 0, find all solutions to the diophantine equation
3a + 3b + 2 = (6j + 2)5 or show that the only solution is (a, b, j) = (3, 1, 0).

Problem 2. For any positive integer n, with (n, 3) = 1, find all solutions to γ3 (nq ) ≤ 3 for q a prime
number where q > 1000?

Problem 3. For any positive integer n, with (n, 3) = 1, we conjecture that γ3 ((6j + 2)5 ) > c ln (6j + 2)5where c is a constant such that 0 < c < 1/(3 ln (3)).
2015.3. Kevin O’Bryant.
Let b1 , b2 , . . . be an infinite binary sequence, and let A be the set of real numbers
P−n . If A has no infinite decreasing subsequence, that is, if A is an ordinal,of the form ai := ∞bn=1 n+i · 2what are the possibilities for the order type of A? In particular, can the order type be ǫ0 ?
Blair, Hamkins, and O’Bryant [forthcoming] have shown that the order type, if infinite, must be at leastω 2 , and can be as large as ω ↑↑ n for any n.
2015.4. Steven Senger (repeat from previous years): Given a large finite subset, A, of real numbers, andany non-degenerate, generalized geometric progression, G, with |G| ≈ |AA|, can we get a nontrivial boundon |(AA + 1)| ∩ G|?
2015.5. Nathan Kaplan: We say a set of points, P ⊂ R2 , is in general position if no curve has more points
than it “ought to”. That is there are no three points on a line, no six points on a conic, etc.... The original
problem posed by Jordan Ellenberg is “How does the minimum height of a set of completely generic points
grow with the number of points?” It is available at:https://quomodocumque.wordpress.com/2014/04/05/
puzzle-low-height-points-in-general-position/

34

MILLER

Can anything be said, even if we choose a greedy construction for our points.
2015.6. Nathan Kaplan (repeat from previous years): In Fn3 , define the function f (n, m) to be the maximum number of lines completely contained in any set of m points. Is it true that the simplest greedy construction (filling in lower dimensional subspaces), is the best possible? That is, is f (n, m) = f (⌈log3 (m)⌉, m)?
2015.7. Kevin O’Bryant: Given a large finite subset, A, of real numbers, is it true that |AA+A| ≥ |A+A|?
Oliver Roche-Newton has asked on Math Overflow(http://mathoverflow.net/questions/204020/
is-the-set-aaa-always-at-least-as-large-as-aa/)
if it is possible for|A · A + A| < |A + A|
with A being a set of real numbers. Some observations.
• For a random set A of k real numbers, A·A+ A has ∼ k 3 /2 elements while A+ A has only ∼ k 2 /2,
so any example needs to have some special structure.
• Modulo 13, the set A = {2, 5, 6, 7, 8, 11} (the set of positive quadratic non-residues, with a modulusp ≡ 1 mod 4), is an example. ă• if | · | means Lebesgue measure, then A = [0, 1/2] is an example, as A · A + A = [0, 3/4] but
A + A = [0, 1].
• if A is a set of 3 or more positive integers, then it cannot be an example, as
a1 + an A, a2 + an A, . . . , an + an A

, where an = max A, are necessarily disjoint (reduce modulo an ) and contain at least |A|2 elements
altogether, while |A + A| ≤ |A|+1.
2
The audience asked what was known for Hausdorff measure, and suggested considering the problem overthe integers, positive rationals, and complexes.

COMBINATORIAL AND ADDITIVE NUMBER THEORY PROBLEM SESSIONS: ’09–’15

2015.8. Speaker List.
• Paul Baginski, Fairfield University• Bela Bajnok, Gettysburg College• Dakota Blair, CUNY Graduate Center• Lisa Bromberg, CUNY Graduate Center• Mei-Chu Chang, University of California• Scott Chapman, Sam Houston State University• David John Covert, University of Missouri St. Louis• Robert Donley, Queensborough Community College (CUNY)• Leonid Gurvits, City College (CUNY)• Sandie Han, New York City Tech (CUNY)• Charles Helou, Penn State Brandywine• Alex Iosevich, University of Rochester• Renling Jin, College of Charleston• Nathan Kaplan, Yale University• Mizan Khan, Eastern Connecticut State University• Sandra Kingan, Brooklyn College (CUNY)• Diego Marques, University of Brasilia• Ariane Masuda, New York City Tech (CUNY)• Nathan McNew, Dartmouth College• Steven J. Miller, Williams College• Mel Nathanson, Lehman College (CUNY)• Kevin O’Bryant, College of Staten Island (CUNY)• Cormac O’Sullivan, Bronx Community College (CUNY)• Jasmine Powell, Northwestern University• Alex Rice, University of Rochester• Steven Senger, Missouri State University• Satyanand Singh, New York City Tech (CUNY)• Jonathan Sondow, New York• Johann Thiel, New York City Tech (CUNY)• Yuri Tschinkel, NYU• Bart Van Steirteghem, Medgar Evers College (CUNY)• Madeleine Weinstein, Harvey Mudd College
A list of talks and abstracts is available online here:
http://www.theoryofnumbers.com/CANT2015-abstracts.pdf.

E-mail address: sjm1@williams.edu, Steven.Miller.MC.96@aya.yale.edu
D EPARTMENT OF M ATHEMATICS AND S TATISTICS , W ILLIAMS C OLLEGE , W ILLIAMSTOWN , MA 01267

35