Arithmetic Progression Hypergraphs:
Examining the Second Moment Method

arXiv:1712.01781v1 [cs.DS] 5 Dec 2017

Michael Mitzenmacher∗
michaelm@eecs.harvard.edu

Abstract
In many data structure settings, it has been shown that using “double hashing” in place of standard
hashing, by which we mean choosing multiple hash values according to an arithmetic progression instead
of choosing each hash value independently, has asymptotically negligible difference in performance. We
attempt to extend these ideas beyond data structure settings by considering how threshold arguments
based on second moment methods can be generalized to “arithmetic progression” versions of problems.
With this motivation, we define a novel “quasi-random” hypergraph model, random arithmetic progression (AP) hypergraphs, which is based on edges that form arithmetic progressions and unifies many
previous problems. Our main result is to show that second moment arguments for 3-NAE-SAT and 2coloring of 3-regular hypergraphs extend to the double hashing setting. We leave several open problems
related to these quasi-random hypergraphs and the thresholds of associated problem variations.

∗

Harvard University, School of Engineering and Applied Sciences. Supported in part by NSF grants CCF-1320231, CNS1228598, IIS-0964473, and CCF-0915922. Part of this work was done while visiting Microsoft Research, New England.

1 Introduction
1.1 Arithmetic Progression Problems
For several multiple-choice hashing data structures, it has been shown that using “double hashing” instead of
uniform hashing yields essentially no difference in performance, in both the asymptotic and practical senses
of performance. For example, consider the balanced allocation setting [4] where n balls are placed into n
bins, but instead of placing them randomly according to a single hash function (assumed to be perfectly
random), each ball is placed sequentially in the least loaded of d choices, each obtained independently by a
hash function, for some constant integer d > 2. The asymptotic fraction of bins of each constant load can be
found by fluid limit differential equations [20], and the maximum load is known to be log log n/ log d+O(1)
with high probability [4]. Now suppose the d choices are chosen in a fashion reminiscent of double hashing,
in the following way. Let us assume that n is prime, and each ball is hashed twice, to obtain a chosen
uniformly from [0, n − 1] and b chosen uniformly from [1, n − 1]. The d choices for a ball are then given by
bins a, a + b, a + 2b, . . . , a + (d − 1)b modulo n. That is, the d choices are constrained to form an arithmetic
progression; as such, only two random numbers modulo n are chosen to determine the choices, instead of
d random numbers. It has been shown that, even with this more limited randomness, not only does the
maximum load remain log log n/ log d + O(1) with high probability, but that the asymptotic fraction of bins
of each constant load is the same as when the d choices are all perfectly random [21, 22]. Similar results
have been found for other data structures that use multiple hash functions, including Bloom filters [17] and
cuckoo hashing [18, 23].
In this paper, we expand on this theme to consider whether similar phenomena occur in “multiplechoice” settings outside of hash-based data structures. Specifically, we attempt to generalize threshold
arguments for variations of random constraint problems found using the second moment method, such as
variations of k-NAE-SAT and 2-coloring random k-uniform hypergraphs. Formalizing these variations lead
us to propose a novel “quasi-random” hypergraph model that we believe is worthy of future study in its own
right; we propose several open questions related to this graph model.
To review, the standard k-NAE-SAT problem is the following: given a collection of variables {x1 , . . . , xn },
and a collection of clauses where each clause consists of k literals on these variables (that is, k variables or
negations of variables), can we assign true/false values to the variables so that each clause has at least one
true and at least one false literal. For the random k-NAE-SAT problem, m clauses are chosen uniformly
at random from the collection of all clauses. (There are variations depending on whether literals for each
clause are chosen with or without replacement; the choice of such details can simplify analysis, but don’t
affect the asymptotic results we consider here.)
Our proposed variation, k-AP-NAE-SAT, adds the following additional requirements: the number of
variables n is prime, and the k variables in each clause must form an arithmetic progression a, a + b, a +
2b, . . . , a + (k − 1)b modulo n. In the random variation, each clause is chosen independently and uniformly
from the 2k n2 possible clauses; that is, the k signs for the literals are chosen independently and uniformly
at random, and we choose values for a and b modulo n independently and uniformly at random to choose
the variables within a clause. Our primary result is that a second moment method argument of Achlioptas
and Moore for random k-NAE-SAT can be applied to random k-AP-NAE-SAT to obtain a lower bound
threshold result for the case where k = 3 [2].
The k-NAE-SAT problem is similar to the hypergraph 2-coloring problem of k-uniform hypergraphs:
given a collection of m hyperedges each of k vertices, can the vertices be colored with two colors so that
each edge has a vertex of each color. Here we consider the variation of 2-coloring hypergraphs, where each
hyperedge consists of vertices that form an arithmetic progression. We again show that a second moment
argument due to Achlioptas and Moore generalizes to this setting when k = 3 [1].
We describe the current impediments to extending these results beyond k = 3, and make corresponding
1

conjectures. More generally, we describe a “quasi-random” hypergraph model where edges are constrained
to form an arithmetic progression that captures these and many other problems. We suggest several open
questions related to this quasi-random hypergraph model.

1.2 Model and Motivation
As described above, we consider variations of random k-NAE-SAT where the variables within a clause
form an arithmetic progression, which may appear to be a somewhat unusual object. We offer multiple
motivations for why this is an interesting problem to study.
Satisfiability problems are a particularly natural problem to consider in this context, as random k-SAT
and variations have been the subject of wide study, with a great deal of work focusing on the thresholds
for satisfiability (see, e.g., [2, 8, 10, 15] and references therein). In particular, there has been some belief
that random problems at or near the threshold boundary may be where “hard instances” lie for NP-complete
variations such as k-SAT [7, 24]. It therefore seems interesting that there may be random k-SAT variations
utilizing much less randomness but that seem to have similar threshold properties; such variations may
prove useful for understanding the complexity of random k-SAT problems or similar problems, or for testing
algorithms for such problems. Indeed, the added structure of arithmetic progressions may potentially make
such problems easier to study in some circumstances.
In considering problems with thresholds, the second moment method is a natural line of attack, given
that it led the way to key threshold results for many problems relatively recently, and is reasonably well
understood. We therefore turn to the seminal results of Achlioptas and Moore [1, 2], which provided a spark
to the area.
While not specifically a hashing problem, random k-SAT problems are similar (and closely connected
to) hashing problems; see e.g. [9]. As previously noted, there are various settings where using double
hashing has essentially the same behavior as hashing with fully random multiple choices. Most of these
hashing problems have natural interpretations as problems on random hypergraphs, by viewing elements
as hyperedges and buckets as vertices in a hypergraph. For example, the question of whether there is an
assignment of elements to buckets in cuckoo hashing is equivalent to the question of whether there is an
orientation of hyperedges in a random hypergraph that does not “overload” any vertex by orienting too
many edges toward it. It therefore seems natural to ask whether other hypergraph problems behave similarly
when using edges based on arithmetic progressions instead of fully random edges.
The double hashing variation of these hashing schemes correspond to the following variations of random
hypergraph models, which appear implicit in previous works but do not seem to have been described. As
mentioned previously, in what follows for convenience we allow for n2 arithmetic progressions on the
numbers modulo n for prime n > 2; we include the trivial progressions (a, a, . . . , a) where all elements are
the same, and we count (a, a + x, a + 2x, . . . , b) and (b, b − x, b − 2x, . . . , a) as distinct progressions for
0 ≤ a < n, 0 < x < n, and b = a + (k − 1)x.
Definition 1. For a prime number n and k < n, let HkAP (n, p) be a random k-uniform hypergraph on n
vertices where where each of the n2 possible edges given by (a, a + x, a + 2x, . . . , a + (k − 1)x) with
0 ≤ a < n and 0 ≤ x < n is included with probability p.
Similarly, let HkAP (n, m) be a random k-uniform hypergraph on n vertices with m edges where the
edges are determined by selecting independently and uniformly at random, with replacement, each edge
from all n2 possible arithmetic progressions.
We may also use the phrasing “a hypergraph chosen from HkAP (n, m)” (or HkAP (n, p)) where the meaning is clear. We suggest referring to these types of hypergraphs as random arithmetic progression hypergraphs, or more succinctly random AP hypergraphs.

2

One can vary this definition to disallow hyperedges with repeated vertices if needed, or to disallow
multi-hyperedges, or to have non-regular edges. Also, we note tht we focus on n prime for convenience, to
avoid asymmetries when b is not relatively prime to n. (In many settings, this issue may ignored without
affecting the asymptotics, or similarly b may instead be restricted to be a randomly chosen number relatively
prime to n.)
The HkAP (n, p) model is a natural “quasi-random” graph model that has not, to our knowledge, been
studied previously. Previous results for hashing schemes suggest it is very like the standard random hypergraph model HkAP (n, p) in useful ways (at least from the algorithmic perspective). We believe this graph
model is worthy of further investigation, as we discuss below.
We correspondingly define variations of the k-SAT problem with the addition of an “AP” to denote that
the variables must be chosen to form an arithmetic progression. Hence instead of k-SAT and k-NAE-SAT,
we may have k-AP-SAT and k-AP-NAE-SAT.

1.3 Result Summary and Some Conjectures
Reviewing previous second moment arguments for threshold behaviors, several of them rely on determining
the distribution of the number of monochromatic collections of k variables for a random coloring of the
variables with two colors (such as “true” of “false” in the k-SAT settings). In the variations we consider
where the variables in our constraints are governed by an arithmetic progression, the relevant question to
consider is the distribution of the number of monochromatic collections of k variables, when the variables
are in an arithmetic progression. For general k, this is a very challenging problem [5, 19, 25], but for the
case of k = 3, the distributions are the same as in the case of complete randomness; we discuss and prove
this below. This simple fact provides our main results.
These results, however, provides some fodder for additional conjectures.
1. Can the second moment method arguments of [1, 2] for k-NAE-SAT, or other second moment arguments (such as in [3, 8]), be made to apply to k-AP-NAE-SAT to obtain corresponding threshold
results for all k ≥ 3? (The same questions can be asked for hypergraph 2-colorability.)
2. There has been further progress on the actual thresholds for k-NAE-SAT and k-SAT using “belief
propagation” based analysis (e.g, [10, 11]). Can these techniques be used and these results be shown
to also hold in the settings of k-AP-NAE-SAT and k-AP-SAT?
We conjecture all of these questions have positive answers. We discuss some of the challenges to proving
the first conjecture below.

2 Second Moment Argument for k-AP-NAE-SAT
2.1 Problem Statement
We consider k-AP-NAE-SAT, following closely the argument of Achlioptas and Moore [2]. We consider
formulas F with variables x1 , x2 , . . . , xn and m = rn clauses. We use the term literal to refer to a variable
or a negated variable. Fitting with our previous discussion, assume n is a prime and F is determined by
choosing each clause independently and uniformly at random from all clauses with k literals with replacement, where the k literals are required to be one of the n2 possible arithmetic progressions modulo n. (The
analysis is easily shown to be essentially the same if the clauses cannot include the trivial clauses and/or are
chosen without replacement; see the discussion for instance in Section 4.1 of [2] showing such variations
affect the threshold by o(1) terms.) We aim to determine as tightly as possible bounds for the threshold for
satisfiability; ideally, we would find a constant r ∗ so that for any constant ǫ > 0, for all r > (r ∗ + ǫ) with
3

high probability a randomly selected formula F would not be satisfiable, while for all r < (r ∗ − ǫ), with
high probability a randomly selected formula F would be satisfiable. Our results will hold only for k = 3,
but we write the argument for general k and later explain why k = 3 is required.

2.2 Adapting the Second Moment Argument
Let X = X(F ) be the number of NAE-satisfying truth assignments for a formula F ; that is, the truth
assignment satisfies that for every clause in F , there is at least one satisfied and at least one unsatisfied
literal. We apply the second moment method as follows. The first moment is simple to compute, and indeed
the fact that the clauses are constrained to be arithmetic progressions does not affect the calculation.
m

,
E[X] = 2n 1 − 21−k
since the probability a clause NAE-satisfies a randomly chosen clause is 1 − 21−k . (In particular, we note
the following well-known result for purely random clauses hold here in the setting of random AP clauses as
well: if m = rn and k = 3, then for r > log4/3 2 ≈ 2.41,
E[X] = 2n (3/4)rn = o(1),
so that first order methods give an upper bound on the satisfiability threshold.)
To compute E[X 2 ], we consider all possible 4n ordered pairs of assignments (σ, τ ). We recall from [2]
that the probability that both σ and τ NAE-satisfy a randomly chosen clause c (from the collection of all
possible clauses with k literals) depends only on the overlap between the assignments. That is, if σ and τ
agree on z = αn variables, then by inclusion-exclusion we find


Pr[σ and τ NAE-satisfy c] = 1 − 22−k + 21−k αk + (1 − α)k .
This is because for a clause c to not be satisfied by both σ and τ , the literals of c must evaluate to all true
or all false in σ and τ . One way of expressing this is that if we consider truth assignments as bit strings
in the natural way (with true being 1 and false being 0), and then consider σ⊕τ as a bit string, a clause
c is not satisfied by both σ and τ if and only if the variables in the clause c are monochromatic in σ⊕τ ;
that is, they must all be 0 or all 1. The probability of a randomly chosen clause c being monochromatic in
this manner is αk + (1 − α)k . (Technically, this is the probability if the variables are not constrained to be
distinct; as mentioned, the difference between allowing or not allowing repeated variables does not affect
the overall threshold argument.) This expression for the probability σ and τ NAE-satisfy c forms the basis
for their calculations regarding bounding the ratio E[X 2 ]/E[X]2 for the remainder of their second moment
argument.
Let us consider E[X 2 ] now where c′ is a randomly chosen clause constrained to be an arithmetic progression. As before, we consider all possible 4n ordered pairs of assignments (σ, τ ). Let β(σ, τ ) be the fraction
of arithmetic progressions of length k in the bit string for σ⊕τ that are monochromatic. The corresponding
inclusion-exclusion for this case give us now:
Pr[σ and τ NAE-satisfy c′ ] = 1 − 22−k + 21−k β(σ, τ ).
For general k, β(σ, τ ) depends on the actual choices of σ and τ . For the case of k = 3, however, we have
that if σ and τ agree on z = αn variables, then β(σ, τ ) is a function of α, and in fact equals α3 + (1 − α)3 .
In particular, we have the following known result:
Lemma 2. For a prime n, a two-coloring of Zn where the two color classes consist of αn numbers and
(1 − α)n numbers has (1 − 3α + 3α2 )n2 = (α3 + (1 − α)3 )n2 monochromatic arithmetic sequence of
length three.
4

Although this result is known in the literature [19], for completeness we provide a proof (suggested to
us by Yufei Zhao) in the appendix.
Because the probability a randomly chosen progression of length three is monochromatic is also (α3 +
(1 − α)3 ), for the second moment calculations of [2], the results when clause variables are constrained to be
arithmetic progression of length three remains the same as if the clause variables were randomly chosen. In
particular, if we let
1 1
f (α) = + (α3 + (1 − α)3 ),
2 4
then following their work, we have
E[X]2 = 2f (α)rn ,
and (letting H(x) be the binary entropy of x)
2

E[X ] =

n  
X
n
z=0

z

f (z/n)m

n

≤ (n + 1) max 2H(α) f (α)r
α

≤ CE[X]2

for some constant C. (We note the second line, bounding E[X 2 ] by CE[X]2 , requires a significant calculation argument, and refer the reader to [2].)
We have the following corollary, which corresponds to the significant work of Lemma 2 and Theorem 5
of [2]:
Corollary 3. For k = 3, when r < 1.5 a random k-AP-NAE-SAT formula is satisfiable with probability
bounded below by some constant.

2.3 Remarks on the Result
We would like to further say that Corollary 3 implies that a random k-AP-NAE-SAT has a solution with
probability 1 − o(1). In [2], the authors rely on the results of Friedgut [15] to claim that the result with
uniformly positive probability can be boosted to with high probability. Specifically, Friedgut’s work is in a
line of results that show for many problems on random graphs and hypergraphs that if there is a threshold, it
must be a “sharp threshold” instead of a “coarse threshold” [6, 13–16]. In particular, this implies that if the
second moment results yield a constant lower bound on the existence of solution, then in fact a solution exists
with high probability. While these results intuitively should also apply as well to the settings of HkAP (n, p)
and HkAP (n, m), it is not immediate that they do so; in particular, these quasi-random hypergraphs do not
have the symmetry properties that fully random hypergraphs do, which are used in many of the existing
proofs. (Some results here do not require complete symmetry, but have other non-trivial requirements.)
We conjecture that the “sharp threshold” framework of Friedgut (and others) can be generalized to the
quasi-random hypergraph models HkAP (n, p) and HkAP (n, m); however, we leave this as an open question.
Naturally, we would also like the result to hold for all constant k, not just k = 3. Recall that the second
moment argument depends on
Pr[σ and τ NAE-satisfy c′ ] = 1 − 22−k + 21−k β(σ, τ ),
where β(σ, τ ) is the fraction of arithmetic progressions of length k in the bit string for σ⊕τ that are
monochromatic. For k = 3, we found this fraction was
fk (α) = 1 − 22−k + 21−k (αk + (1 − α)k )
5

for every σ and τ . Unfortunately, for k > 3, the fraction of arithmetic progressions of length k that
monochromatic varies with σ and τ .
One might hope that, say for randomly chosen σ and τ , the fraction of monochromatic arithmetic progressions in σ⊕τ would be well concentrated around fk (α), and this would be sufficient to bound the second
moment and apply the second moment method. Chernoff-like concentration bounds for this setting do exist
[5,25], but it is also known that the number of arithmetic progressions can differ significantly from the mean
(see, e.g., [19]). The second moment argument of Achlioptas and Moore is, unfortunately for us, rather
n
precise. Recall E[X 2 ] is bounded by above by (n + 1) maxα 2H(α) fk (α)r , increasing fk (α) by even
an ǫ-size constant increase E[X 2 ] exponentially, and the second moment bound is lost. We optimistically
conjecture that the second moment method can be generalized for k > 3, but it (currently) appears difficult;
it may require a different approach to bounding E[X 2 ] rather than considering how β(σ, τ ) depends on the
overlap α. Possibly, the second moment method may not be suitable for finding thresholds for general k,
and other approaches (as in [10, 11]) may be required.

3 Second Moment Argument for Hypergraph 2-Colorability
3.1 Adapting the Second Moment Argument
We can similarly consider the second moment method with for hypergraph 2-colorability, another problem
considered in [1, 2]. Here we follow the argument of [1].1
Let X be the number of 2-colorings of a hypergraph chosen from HkAP (n, m), with m = rn again. We
apply the second moment method as follows, for the case where k = 3. The probability that a 2-coloring
with z = αn black vertices and n = z = (1 − α)n white vertices makes a random hyperedge bichromatic is
1 − 3α + 3α2 = 1 − α3 − (1 − α)3 ,
based on Lemma 2, just as it would be for a standard randomly hypergraph. Thus
n  
X
n
E[X] =
(1 − (z/n)3 − (1 − z/n)3 )rn .
z
z=0

Note that in this settings this expectation result cannot be generalized when k > 3, since as we have
discussed the number monochromatic hyperedges would not depend only on the fraction of vertices of each
color.
To bound E[X 2 ], consider a pair of 2-colorings S and T with αn and βn black vertices respectively, and
γn vertices that are black in both. As described in [1], for a standard random hypergraph, the probability a
random hyperedge of size k would be bichromatic under both S and T is given by:
1 − αk − (1 − α)k − β k − (1 − β)k + γ k + (α − γ)k + (β − γ)k + (1 − α − β + γ)k .
For the case of k = 3, the above expression holds also for hypergraphs chosen from HkAP (n, m), again
because of Lemma 2. Let the expression above be denoted by p(α, β, γ). Achlioptas and Moore provide the
following expression for E[X 2 ] in the setting of standard hypergraphs, which carries over here as well:

 
X 
n
z1 + z2 z1 + z3 z3 rn
2
,
,
,
E[X ] =
p
n
n
n
z1 , z2 , z3 , z4
z ,z ,z ,z
1

2

3

4

1

In [2], Achlioptas and Moore provided a more sophisticated argument with a simpler overall calculation, by considering
balanced colorings, where the number of vertices of each color are the same. In our case, since the number of vertices is odd,
we cannot follow their argument completely, although it appears that the natural approach of considering near-balanced colorings
⌊n/2⌋ vertices of the first color and ⌈n/2⌉ vertices of the second color would allow us to mimic their argument. Because here we
are using their mathematical derivations as a black box, it suffices to use the approach of [1], which yields the same result.

6

where z1 is the number of vertices colored black in both assignments, z2 is the number of vertices colored
black in S and white in T , z3 is the number of vertices colored white in S and black in T , and z4 is the
number of vertices colored white in both assignments.
Given these expression for E[X] and E[X 2 ], Achlioptas and Moore show that the dominant when calculating the ratio between E[X 2 ] and E[X]2 for the second moment method is when α = β = 1/2 and
γ = 1/4; again, their calculations for the standard hypergraph case carry over to the case of k = 3 here,
yielding the following final result.
Theorem 4. For a random hypergraph HkAP (n, m) with m = rn, r < 3/2, the hypergraph is 2-colorable
with uniform positive probability.

3.2 Remarks on the Result
Again, we would like the with uniform positive probability result here to yield a with high probability result.
The 2-colorability threshold of standard random hypergraphs is considered explicitly by Friedgut [14], who
shows that there is a non-uniform sharp threshold for hypergraph 2-colorability, which implies that in the
context of standard hypergraphs, the result with uniform positive probability implies a with high probability
result. We conjecture that the same holds here; however, the explicit proof by Friedgut depends on a result
by Erdös and Simonovits on random t-partite systems [12]. It is an interesting question as to whether that
result can generalize to the setting of hyperedges governed by arithmetic progressions.
Also, as with k-AP-NAE-SAT, it remains a challenge to obtain second moment results for k > 3.

4 Conclusion
Motivated by recent results in double hashing, we have introduced quasi-random hypergraphs that we refer
to as random AP hypergraphs. Given that random AP hypergraphs have implicitly arisen in the study
of multiple-choice hashing data structures, they appear worthy of future study. We have conjectured that
random AP hypergraphs share the same thresholds as standard hypergrpahs with regard to 2-colorability,
and have correspondingly defined AP versions of random satisfiability problems, which we also conjecture
share the same satisfiability thresholds as their standard counterparts. We have shown that second moment
arguments for thresholds for these problems generalize when k = 3. We have also conjectured that the
sharp/coarse threshold results of Friedgut (and others) apply to random AP hypergraphs as well.
At a higher level, it seems worthwhile to understand more clearly how random AP hypergraphs are
essentially similar to (and different from) standard hypergraphs in generally usable ways. Perhaps there is
some abstractable high-level property shared by random AP and standard hypergraphs that would provide
a mechanism for easily showing double hashing versions of hashing data structures have the same performance as standard versions, without an ad hoc analysis for each data structure. At the same time, it would
be useful to understand how random AP hypergraphs are different from standard hypergraphs; there should
be settings where the use of less randomness and/or specifically the arithmetic progression constraint has a
significant algorithmic or complexity-related effect.

Acknowledgments
The author thanks Cris Moore for several helpful discussions, and Yufei Zhao for explaining results regarding monochromatic colorings of arithmetic progressions of length 3.

7

References
[1] Dimitris Achlioptas and Cristopher Moore. On the 2-colorability of random hypergraphs. In Proceedings of the 6th International Workshop on Randomization and Approximation Techniques in Computer
Science, pages 953–953. Springer, 2002.
[2] Dimitris Achlioptas and Cristopher Moore. Random k-sat: two moments suffice to cross a sharp
threshold. SIAM Journal on Computing, 36(3):740–762, 2006.
[3] Dimitris Achlioptas and Yuval Peres. The threshold for random k-sat is 2k log 2 − o(k). Journal of the
American Mathematical Society, 17(4):947–973, 2004.
[4] Yossi Azar, Andrei Z Broder, Anna R Karlin, and Eli Upfal. Balanced allocations. SIAM journal on
computing, 29(1):180–200, 1999.
[5] Bhaswar B Bhattacharya, Shirshendu Ganguly, Xuancheng Shao, and Yufei Zhao. Upper tails for
arithmetic progressions in a random set. arXiv preprint arXiv:1605.02994, 2016.
[6] Jean Bourgain and Gil Kalai. Influences of variables and threshold intervals under group symmetries.
Geometric and Functional Analysis, 7(3):438–461, 1997.
[7] Peter C Cheeseman, Bob Kanefsky, and William M Taylor. Where the really hard problems are. In
IJCAI, volume 1, pages 331–337, 1991.
[8] Amin Coja-Oglan and Konstantinos Panagiotou. Catching the k-naesat threshold. In Proceedings of
the Forty-Fourth Annual ACM Symposium on Theory of Computing, pages 899–908. ACM, 2012.
[9] Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh,
and Michael Rink. Tight thresholds for cuckoo hashing via XORSAT. In Proceedings of the 37th
International Colloquium on Automata, Languages and Programming, pages 213–225. Springer, 2010.
[10] Jian Ding, Allan Sly, and Nike Sun. Proof of the satisfiability conjecture for large k. In Proceedings
of the Forty-Seventh Annual ACM Symposium on Theory of Computing, pages 59–68. ACM, 2015.
[11] Jian Ding, Allan Sly, and Nike Sun. Satisfiability threshold for random regular nae-sat. Communications in Mathematical Physics, 341(2):435–489, 2016.
[12] Paul Erdős and Miklós Simonovits. Supersaturated graphs and hypergraphs. Combinatorica, 3(2):181–
192, 1983.
[13] Ehud Friedgut. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27–35, 1998.
[14] Ehud Friedgut. Hunting for sharp thresholds. Random Structures & Algorithms, 26(1-2):37–51, 2005.
[15] Ehud Friedgut and Jean Bourgain. Sharp thresholds of graph properties, and the k-sat problem. Journal
of the American Mathematical Society, 12(4):1017–1054, 1999.
[16] Ehud Friedgut and Gil Kalai. Every monotone graph property has a sharp threshold. Proceedings of
the American Mathematical Society, 124(10):2993–3002, 1996.
[17] Adam Kirsch and Michael Mitzenmacher. Less hashing, same performance: Building a better bloom
filter. Random Structures & Algorithms, 33(2):187–218, 2008.
8

[18] Mathieu Leconte. Double hashing thresholds via local weak convergence. In Proceedings of the
51st Annual Allerton Conference on Communication, Control, and Computing, pages 131–137. IEEE,
2013.
[19] Linyuan Lu and Xing Peng. Monochromatic 4-term arithmetic progressions in 2-colorings of zn .
Journal of Combinatorial Theory, Series A, 119(5):1048–1065, 2012.
[20] Michael Mitzenmacher. Studying balanced allocations with differential equations. Combinatorics,
Probability and Computing, 8(5):473–482, 1999.
[21] Michael Mitzenmacher. Balanced allocations and double hashing. In Proceedings of the 26th ACM
Symposium on Parallelism in Algorithms and Architectures, pages 331–342. ACM, 2014.
[22] Michael Mitzenmacher. More analysis of double hashing for balanced allocations. In Proceedings of
the Thirteenth Workshop on Analytic Algorithmics and Combinatorics, pages 1–9. SIAM, 2016.
[23] Michael Mitzenmacher and Justin Thaler. Peeling arguments and double hashing. In Proceedings of
the 50th Annual Allerton Conference on Communication, Control, and Computing, pages 1118–1125.
IEEE, 2012.
[24] Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, and Lidror Troyansky. Determining computational complexity from characteristic’phase transitions’. nature, 400(6740):133, 1999.
[25] Lutz Warnke.
Upper tails for arithmetic progressions in random subsets.
arXiv:1612.08559, 2016.

arXiv preprint

Appendix
Lemma 2. For a prime n, a two-coloring of Zn where the two color classes consist of αn numbers and
(1 − α)n numbers has (1 − 3α + 3α2 )n2 monochromatic arithmetic sequence of length three.
Proof of Lemma 2. Let zi be a variable for 0 ≤ i < n, S be the set of all n2 arithmetic progressions of
length three given as ordered triples, and consider the polynomial
X
(zi zj zk + (1 − zi )(1 − zj )(1 − zk )).
(i,j,k)∈S

Now consider this polynomial for a given two-coloring of Zn with zi being the color of i ∈ Zn , and where
one color class corresponds to zi = 0 and the other corresponds to zi = 1. The summation above then
equals the number of monochromatic arithmetic sequences, since each element in the sum is 1 if the triple
(i, j, k) corresponds to a monochromatic arithmetic sequence and 0 otherwise. Expanding, we find
X
X
(zi zj zk + (1 − zi )(1 − zj )(1 − zk )) =
(1 − zi − zj − zk + zi zj + zj zk + zi zk )
(i,j,k)∈S

(i,j,k)∈S

= n2 − 3n(αn) + 3(αn)(αn)
= (1 − 3α + 3α2 )n2 .
Note that for the second equality, we use that there are n2 triples in S; there are 3n triples in S including
i for the αn values of zi with zi = 1 (counting the triple (i, i, i) three times); and there are 3 triples in S
including i and j for every ordered pair zi and zj with zi zj = 1 (again counting the triple (i, i, i) three times
when i = j).

9

