子集的Gowers范数与伪随机测度

Gowers Norm and Pseudorandom Measures of Subsets

设A■ZN,以及fA(s)={1-|A|/N,若s∈A,-|A|/N,若s■A,本文定义子集A的k阶伪随机测度如下:Pk(A,N)=maxD|n∈ZN∑fA(n+c1)fA(n+c2)…fA(n+ck),其中max表示对所有满足0≤c1<c2<…<ck≤N-1的D=(c1,c2,…,ck)∈Z^k取最大值。当Pk(A,N)是N的无穷小量时,称A■ ZN为k阶伪随机子集。本文将建立Gowers范数与伪随机测度之间的联系,证明“好”的伪随机子集一定有“小”的Gowers范数,同时举例说明其逆命题并不成立。本文还证明了L(k)阶伪随机子集包含长度为k的等差数列,其中L(k)=2·lcm(2,4,…,2[2/k]),此处k≥4,lcm(a1,a2,…,a1)表示a1,a2,…,al的最小公倍数。

Let A ■ ZN,and fA(s)={1-N/|A|for s ∈A,-N/|A| for s ■A.We define the pseudorandom measure of order k of the subset A as follows,Pk(A,N)=maxD|n∈ZN∑fA(n+c1)fA(n+c2)…fA(n+ck),where the maximum is taken over all D=(c1,c2,…,ck)∈Z^k with 0≤c1<c2<…ck≤N-1.The subset A ■ZN is considered as a pseudorandom subset of degree k if P上(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 pseudorandom subset of degree L(k) contains an arithmetic progression of length k, where L(k)=2·lcm(2,4,…,2[2/k]),for k≥4 and lcm(ai, a2,…,al)denotes the least common multiple of a1,a2,…, al.