WorksMathematics
A lower bound for the four-dimensional Erdős box problem
Abstract
For every power of~, we construct a box-free subset of with points, improving the lower-bound exponent in the four-dimensional Erdős box problem from to . In fact, partitions into isomorphic box-free sets. The proof uses a finite-field rectangle lemma and orthogonality in a four-dimensional bilinear space. We also deduce a uniform bound and a lower bound for grid-coloring numbers.
Introduction
A box in a product is a set with for all . A set is box-free if it contains no box. Let be the maximum size of a box-free subset of , where . Equivalently, is the maximum number of edges in an -partite -uniform hypergraph with vertices in each part and no copy of .
Erdős [3] proved that and conjectured that this is the correct order of magnitude. The conjecture is known for [6]. For , Gunderson, Rödl, and Sidorenko [5] obtained the lower bound , subsequently recovered by Conlon, Pohoata, and Zakharov [1] and Gordeev [4]. We improve the lower-bound exponent to .
Theorem 1. For every power of 2, there is a box-free subset of of size . Moreover, partitions into isomorphic box-free subsets.
The construction uses the inverse of the permutation of . A rectangle lemma shows that four points of the form are either collinear or affinely independent over . This dichotomy, together with a bilinear pairing, rules out boxes. We give the lemma and the proof, then deduce the uniform lower bound and the coloring consequence.
A finite-field rectangle lemma
Fix a power of 2, and write and . The relative trace and norm are
Since for , the trace pairing is nondegenerate: for , take . Also, if and only if .
Set . Expanding and using gives
Thus implies , so permutes . Its polarization
is symmetric and -bilinear, with . Applying (2.1) to and shows that . Moreover, if and only if are linearly dependent over : when , this equation is equivalent to .
The next lemma gives the dichotomy used in the construction. We include the proof, following [6 Lemma 3.2].
Lemma 2. Let , and put
If and , then either the four points are affinely independent over , or they are collinear and satisfy
If or , both sums vanish.
Proof. If or , the entries occur in equal pairs and both sums vanish. Assume that and , and set
Then and . Summing and expanding gives
Multiplying by and taking the trace yields
The -trilinear form is alternating, since it vanishes whenever two arguments coincide. If , then , so are linearly independent and the four points are affinely independent.
If , equation (2.2) gives . Hence for some , and the points are collinear. Finally, (2.1) gives
The construction
Continue with , , from Section 2. Equip with the nondegenerate symmetric bilinear form
and put , so . For and in , define the pair-map by
Let , so . Write a vertex as , where . Define by
The pairing will make the two difference spaces of a box orthogonal. The asymmetric trace term in forces a two-dimensional difference space to contain when both -coordinates vary; the terms rule out the case when neither varies.
Proof of Theorem 1. In (3.1), the first three vertices and determine uniquely for any prescribed value of . Thus every fiber has points. The translation carries onto and preserves boxes. It therefore suffices to prove that is box-free.
Suppose that contains a box with vertices , where , , and . Comparing two corners differing only in part shows that would force . Since the vertices in each part are distinct, we have
For , put
and define
The corner equations have the separated form
where
Taking a difference in each index pair gives
Thus , and nondegeneracy gives
Summing (3.3) over at also gives
We claim that , and that whenever . There are three cases. If neither nor varies, then (4) forces both and to vary. But , contradicting (7).
If exactly one of varies, the difference in the other coordinate is a nonzero multiple of . The difference in the varying coordinate has a nonzero -component. Since , these two differences span . Hence and .
Suppose that both vary, and let be the -components of . If the four points are affinely independent, then . Otherwise, Lemma 2 gives
Consequently, . The projection of onto is one-dimensional and nonzero, while the kernel of that projection is . Thus and .
The same claim holds for . By (6), both spaces have dimension 2 and contain . Their orthogonality gives the contradiction
Consequences
We first pass from powers of to arbitrary side lengths.
Corollary 3. For every integer ,
Moreover, .
Proof. If a box-free set is restricted to independently chosen, uniformly random -element subsets of the four parts, where , its expected size is . Hence
For , let be the largest power of 2 with , and write , where . Embedding the construction at and sampling the construction at give
because the two coefficients agree at , with the first decreasing and the second increasing. For , sampling at gives , while . Finally, gives the limsup assertion.
For , let be the least integer such that every -coloring of contains a monochromatic box .
Corollary 4. For every power of 2, we have . For every integer ,
In particular, .
Proof. The coloring in Theorem 1 gives . For , let be the largest power of 2 not exceeding . Since , monotonicity gives .
The known exponents and differ by . It remains open whether the upper exponent is attainable, whether the construction can be extended to more dimensions, and what the correct growth rate of is.
References
- [1]D. Conlon, C. Pohoata, and D. Zakharov, Random multilinear maps and the Erdős box problem, Discrete Anal. (2021), Paper No. 17, 8 pp.arxiv.org/abs/2011.09024
- [3]P. Erdős, On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964), 183–190.DOI
- [4]A. Gordeev, Combinatorial Nullstellensatz and Turán numbers of complete r-partite r-uniform hypergraphs, Discrete Math. 347 (2024), no. 7, Paper No. 114037; corrigendum, Discrete Math. 348 (2025), no. 4, Paper No. 114417.DOI
- [5]D. S. Gunderson, V. Rödl, and A. Sidorenko, Extremal problems for sets forming Boolean algebras and complete partite hypergraphs, J. Combin. Theory Ser. A 88 (1999), no. 2, 342–367.DOI
- [6]D. Menezes, The three-dimensional Erdős box problem has exponent 11/4, arXiv preprint arXiv:2609.22381v2 [math.CO] (2026).arxiv.org/abs/2609.22381