Gowers norms and pseudorandom measures of subsets

Abstract

Let $A \subset {{\Bbb Z}_N}$, and

${f_A}(s) = \left\{ {\begin{array}{*{20}{l}}{1 - \frac{{|A|}}{N},}&{{\rm{for}}\;s \in A,}\\{ - \frac{{|A|}}{N},}&{{\rm{for}}\;s \notin A.}\end{array}} \right.$

We define the pseudorandom measure of order k of the subset A as follows,

P_k(A, N) = $\begin{array}{*{20}{c}}{\max }\\D\end{array}$|$\mathop \Sigma \limits_{n \in {\mathbb{Z}_N}}$f_A(n + c₁)f_A(n + c₂) … f_A(n + c_k)|,

where the maximum is taken over all D = (c₁, c₂, . . . , c_k) ∈ ${\mathbb{Z}^k}$ with 0 ≤ c₁ < c₂ < … < c_k ≤ N - 1. The subset A ⊂ ${{\mathbb{Z}_N}}$ is considered as a pseudorandom subset of degree k if P_k(A, N) is “small” in terms of N. We establish a link between the Gowers norm and our pseudorandom measure, and show that “good” pseudorandom subsets must have “small” Gowers norm. We give an example to suggest that subsets with “small” Gowers norm may have large pseudorandom measure. Finally, we prove that the pseudorandom subset of degree L(k) contains an arithmetic progression of length k, where

L(k) = 2·lcm(2, 4, . . . , 2|$\frac{k}{2}$|), for k ≥ 4,

and lcm(a₁, a₂, . . . , a_l) denotes the least common multiple of a₁, a₂, . . . , a_l.

Keywords

Gowers norm / pseudorandom measure / subset / arithmetic progression

References

[1] Chen Z X . Large families of pseudo-random subsets formed by generalized cyclotomic classes. Monatsh Math, 2010, 161 (2): 161- 172

[2] Dartyge C , Mosaki E , Sárközy A . On large families of subsets of the set of the integers not exceeding N. Ramanujan J, 2009, 18 (2): 209- 229

[3] Dartyge C , Sárközy A . On pseudo-random subsets of the set of the integers not exceeding N. Period Math Hungar, 2007, 54 (2): 183- 200

[4] Dartyge C , Sárközy A . Large families of pseudorandom subsets formed by power residues. Unif Distrib Theory, 2007, 2 (2): 73- 88

[5] Dartyge C , Sárközy A , Szalay M . On the pseudo-randomness of subsets related to primitive roots. Combinatorica, 2010, 30 (2): 139- 162

[6] Furstenberg H . Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions. J Analyse Math, 1977, 31 (1): 204- 256

[7] Furstenberg H , Katznelson Y , Ornstein D . The ergodic theoretical proof of Szemerédi’s theorem. Bull Amer Math Soc, 1982, 7 (3): 527- 552

[8] Goubin L , Mauduit C , Sárközy A . Construction of large families of pseudorandom binary sequences. J Number Theory, 2004, 106 (1): 56- 69

[9] Gowers W T . A new proof of Szemerédi’s theorem. Geom Funct Anal, 2001, 11 (3): 465- 588

[10] Green B , Tao T . An inverse theorem for the Gowers U³(G) norm. Proc Edinb Math Soc, 2008, 51 (1): 73- 153

[11] Liu H N . Large family of pseudorandom subsets of the set of the integers not exceeding N. Int J Number Theory, 2014, 10 (5): 1121- 1141

[12] Liu H N , Song E P . A note on pseudorandom subsets formed by generalized cyclotomic classes. Publ Math Debrecen, 2014, 85 (3/4): 257- 271

[13] Liu H N , Wang X Y . On the correlation of pseudorandom binary sequences using additive characters. Publ Math Debrecen, 2011, 79 (1/2): 145- 170

[14] Mauduit C , Sárközy A . On finite pseudorandom binary sequences, I. measure of pseudorandomness, the Legendre symbol. Acta Arith, 1997, 82 (4): 365- 377

[15] Roth K F . On certain sets of integers. J London Math Soc, 1953, 28 (1): 104- 109

[16] Szemerédi E . On sets of integers containing no k elements in arithmetic progression. Acta Arith, 1975, 27: 199- 245

[17] Yu K T . On a trigonometric inequality of Vinogradov. J Number Theory, 1994, 49 (3): 287- 294

RIGHTS & PERMISSIONS

Higher Education Press