Search for: All records

Celebrated theorems of Roth and of Matoušek and Spencer together show that the discrepancy of arithmetic progressions in the first $$n$$ positive integers is $$\Theta (n^{1/4})$$ . We study the analogous problem in the $$\mathbb {Z}_n$$ setting. We asymptotically determine the logarithm of the discrepancy of arithmetic progressions in $$\mathbb {Z}_n$$ for all positive integer $$n$$ . We further determine up to a constant factor the discrepancy of arithmetic progressions in $$\mathbb {Z}_n$$ for many $$n$$ . For example, if $n=p^k$ is a prime power, then the discrepancy of arithmetic progressions in $$\mathbb {Z}_n$$ is $$\Theta (n^{1/3+r_k/(6k)})$$ , where $$r_k \in \{0,1,2\}$$ is the remainder when $$k$$ is divided by $$3$$ . This solves a problem of Hebbinghaus and Srivastav. 

Abstract May the triforce be the 3-uniform hypergraph on six vertices with edges {123′, 12′3, 1′23}. We show that the minimum triforce density in a 3-uniform hypergraph of edge density δ is δ 4– o (1) but not O ( δ 4 ). Let M ( δ ) be the maximum number such that the following holds: for every ∊ > 0 and $$G = {\mathbb{F}}_2^n$$ with n sufficiently large, if A ⊆ G × G with A ≥ δ | G | 2 , then there exists a nonzero “popular difference” d ∈ G such that the number of “corners” ( x , y ), ( x + d , y ), ( x , y + d ) ∈ A is at least ( M ( δ )–∊)| G | 2 . As a corollary via a recent result of Mandache, we conclude that M ( δ ) = δ 4– o (1) and M ( δ ) = ω ( δ 4 ). On the other hand, for 0 < δ < 1/2 and sufficiently large N , there exists A ⊆ [ N ] 3 with | A | ≥ δN 3 such that for every d ≠ 0, the number of corners ( x , y , z ), ( x + d , y , z ), ( x , y + d , z ), ( x , y , z + d ) ∈ A is at most δ c log(1/ δ ) N 3 . A similar bound holds in higher dimensions, or for any configuration with at least 5 points or affine dimension at least 3.