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.

Key words： 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