Monthly Archive

You are currently browsing the monthly archive for janvier 2017.

Minimum number of patterns at fixed density

02/01/2017 in Uncategorized | Laisser un commentaire

Given a compact abelian group G, endowed with a Haar probability measure \mu, let \mathcal{F}_a be the set of (Borel) measurable functions G\rightarrow [0,1] satisfying \int_G fd\mu \geq \alpha. The average of f is called its density.

Let \Psi be system of linear forms, i.e \Psi=(\psi_1,\ldots,\psi_t): G^d\rightarrow G^t and

\displaystyle{\psi_i(x_1,\ldots,x_d)=\sum_{j=1}^dc_{i,j}x_j}

where c_{i,j}\in\mathbb{Z} for any i\in[t] and j\in[d]. For a measurable function f : G\rightarrow [0,1], one may define the \Psi-count of f as

\displaystyle{T_\Psi(f)=\int_{G^d}\prod_i f(\psi_i(x))d\mu(x).}

Here by a slight abuse of notation, the measure \mu on G^d denotes in fact the product measure \mu^{\otimes d} of the Haar measure on G.

Let

\displaystyle{m_\Psi(\alpha,G)=\inf_{f\in\mathcal{F}_a}T_\Psi(f).}

When a system \Psi is fixed, we may omit it from the notation m_\Psi. Given a sequence G_n of finite groups of cardinality tending to infinity, it is natural to consider the sequence m(\alpha,G_n). When the infimum is taken only over \{0,1\}-valued measurable functions of density at least \alpha, this is the minimum number of APs a set A\subset G_n of density at least \alpha can have. But these infimum are actually the same (basically by convexity).

The case G_n=\mathbb{Z}/n\mathbb{Z} was introduced by Croot. He proved that the minimal density m(\alpha,\mathbb{Z}_N) of three-term arithmetic progressions converged as N\rightarrow\infty through the primes. Sisask, in his PhD thesis, was able to express this limit as an integral over the corresponding limit object, namely the circle \mathbb{T}=\mathbb{R}/\mathbb{Z}, thus

\displaystyle{\lim_{\substack{N\rightarrow +\infty\\ N\text{ prime}}} m(\alpha,\mathbb{Z}_N)=m(\alpha,\mathbb{T}).}

As customary, the corresponding problem in finite field models is cleaner. Thus we set G_n=\mathbb{F}_p^n. Whereas Croot noticed that the sequence m(\alpha,\mathbb{Z}_N) was in some sense approximately decreasing, it is easy to see that for any system \Psi, the sequence m_\Psi(\alpha,G_n) is genuinely non-increasing. This is because \mathbb{F}_p^n embeds naturally in \mathbb{F}_p^{n+1}; thus if f is a map from \mathbb{F}_p^n to [0,1], it can be extended into \tilde{f} : \mathbb{F}_p^{n+1}\rightarrow [0,1] by putting \tilde{f}(x_1,\ldots,x_{n+1})=f(x_1,\ldots,x_n).

Now \mathbb{E} \tilde{f}=\mathbb{E}f, and T_\Psi(f)=T_\Psi(f). This proves that m_\Psi(\alpha,G_n)\geq m_\Psi(\alpha,G_{n+1}), which implies that this sequence has a limit.

Let \Psi be now fixed. We want to find an appealing expression for the limit of the sequence m(\alpha,G_n). It is thus tempting to look for a natural topological compact group that would play the role of limit object of the sequence G_n, just as \mathbb{T} played the role of limit object for the sequence \mathbb{Z}/N\mathbb{Z}.

The analogy \mathbb{Z}\leftrightarrow \mathbb{F}_p[t]=\cup \mathbb{F}_p^n=\mathbb{F}_p^{\infty} leads one to introducing G_\mathbb{N}=\mathbb{F}_p^\mathbb{N} and G_\infty=\mathbb{F}_p^{\infty}. The group G_\mathbb{N} equipped with the product topology is a compact group by Tychonoff’s theorem, and G_\infty equipped with the discrete topology is locally compact; it is the Pontryagin dual of G_\mathbb{N}. It is now reasonable to ask whether

\displaystyle{\lim m(\alpha,G_n)=m(\alpha, G_\mathbb{N}).}

One easily notices that m(\alpha,G_n)\geq m(\alpha, G_\mathbb{N}) for any n\in\mathbb{N} by extending, as above, a function f : \mathbb{F}_p^n \rightarrow [0,1] into a function \tilde{f} on \mathbb{F}_p^\mathbb{N} with the same density and the same \Psi-count. Indeed, one can define

\displaystyle{\tilde{f}((x_i)_{i\in\mathbb{N}})=f(x_1,\ldots,x_n)}

and then \tilde{f} is a measurable function which has same density and same \Psi-count.

We prove the other inequality. For this we prove two intermediate propositions. We write from henceforth G=G_\mathbb{N}.

Proposition 1

If f_n is a sequence of [0,1]-valued functions on G that converges in L^2(G) to a [0,1]-valued function f, then T(f_n)\rightarrow T(f).

Proof

Let F_n(x)=\prod_{i\in[t]} f_n(\psi_i(x))-\prod_{i\in[t]} f(\psi_i(x)). We show that F_n converges in L^1(G^d) to 0, which will conclude. In fact we prove a stronger convergence, a convergence in L^2. We show that \lVert F_n-F\rVert_{2}\leq t \lVert f_n-f\rVert_2. For that we simply remark that

\displaystyle{F_n(x)=\sum_{j=1}^{t}\prod_{i<j}f_n(\psi_i(x))(f_n(\psi_j(x))-f(\psi_j(x)))\prod_{k>j}f(\psi_k(x)).}

Now, any non-trivial linear map \theta : G^d\rightarrow G, i.e. any map of the form

\displaystyle{\theta(x_1,\ldots,x_d)=\sum_{i=1}^d c_ix_i.}

with (c_1,\ldots,c_d)\in \mathbb{F}_p^d\setminus\{0\}, preserves the Haar measure, which implies that

\displaystyle{\lVert f_n\circ\psi_j-f\circ\psi_j\rVert_{L^2(G^d)}=\lVert f_n-f\rVert_{L^2(G)}.}

Using this, the triangle equality and the fact that the functions are 1-bounded, we conclude.

Proposition 2

Let \mathcal{F}_{a,n} be the set of functions \tilde{f} for f : G_n\rightarrow [0,1] of density at least \alpha. Then \mathcal{F}_{a,n} is dense in (\mathcal{F}_a, \lVert \cdot\rVert_2).

Proof

Let f\in\mathcal{F}_a. We construct a sequence of functions f_n\in\mathcal{F}_{a,n} that converge to f. We use duality and Fourier transform. We have \hat{G_n}=G_n and \hat{G_\mathbb{N}}=G_\infty=\cup G_n.

For \chi\in G_\infty, write

transfofourier

Then write

suitefn

This defines a function f_n : G_n \rightarrow \mathbb{C}, which obviously satisfies

egalft.

The same holds for its extension \tilde{f_n}. Notice that \tilde{f_n} is also the conditional expectation with respect to the \sigma-algebra \mathcal{P}(G_n). More precisely,

\displaystyle{f_n(x_1,\ldots,x_n)=\mathbb{E}_{y\in G}(f(y)\mid (y_1,\ldots,y_n)=(x_1,\ldots,x_n))}

as both equal probacondi.

This implies in particular that f_n, and thus \tilde{f_n}, has its values in [0,1].

To check that \mathbb{E} f_n \geq \alpha, we use the conditional expectation interpretation

\displaystyle{\mathbb{E}[f_n]=\mathbb{E}[\mathbb{E}[f\mid G_n]]=\mathbb{E}[f]\geq \alpha.}

Now we check the convergence. It follows from basic harmonic analysis: f being in L^2(G), its Fourier series f_n converges to f in L^2(G). This concludes the proof of Proposition 2.

Thus even for 4-APs, this shows that

\displaystyle{\lim_{n\rightarrow\infty}\inf_{f:\mathbb{F}_p^n\rightarrow[0,1],\mathbb{E}f\geq\alpha}\mathbb{E}_{x,y}f(x)f(x+y)f(x+2y)f(x+3y)}

exists and equals

\displaystyle{\inf_{f:\mathbb{F}_p^\mathbb{N}\rightarrow[0,1],\int f\geq \alpha}\int f(x)f(x+y)f(x+2y)f(x+3y)dxdy.}

This is in contrast to a paper of Candela-Szegedy, for the same pattern \Psi (4-APs) but with G_n=\mathbb{Z}/n\mathbb{Z} where they obtain as a limit a much more complicated infimum, an infimum over functions f on \mathbb{T}^2 of the \Psi'-count, where \Psi'\neq\Psi is another pattern. The part that holds in the setting of \mathbb{F}_p^n and not in the setting of \mathbb{Z}_p is Proposition 2. The truncated Fourier series of f : \mathbb{T}\rightarrow[0,1], which is the natural L^2 approximation, does not give a function on cyclic groups \mathbb{Z}_p with the same density and AP-count as f.

We remark that the paper of Hatami-Hatami-Hirst implies that the sequence of functions f_n admits a limit object g which is defined on a finite cartesian power of G_\mathbb{N}.

In fact, if \Psi is the k-APs, pattern of complexity k-2, and p\geq k, the limit object g is defined on G_\mathbb{N}^{k-2}. In particular, if k=3, this means that the infimum above is attained, i.e.

\lim_{n\rightarrow \infty}m(\alpha, G_n)=T(g)

for some g : \mathbb{F}_p^\mathbb{N}\rightarrow [0,1] measurable. When gnzn, it is still not known whether such a result (i.e. the existence of a limit object g : \mathbb{T}\rightarrow [0,1]) holds. However, Szegedy proves the existence of a limit object g : X\rightarrow [0,1] on a non-explicit group X.