Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 82 / Section B

Use the density form of the Szemerédi theorem: for fixed $\alpha >0$ and length $r$, every sufficiently large subset of $\{1,\dots ,N\}$ of size at least $\alpha N$ contains a nonconstant arithmetic progression of length $r$, as established in Szemerédi's density theorem. This theorem supplies a progression, not the desired averaging configuration; we now select the actual indices.

Take $r=2k+1$. Write the resulting progression asand put $y=a+kd\in A$. If $k=2m$ is even, select $y-d,y+d,\dots ,y-md,y+md$. These are $2m=k$ distinct members of the progression, and each opposite pair sums to $2y$. If $k=2m+1$ is odd, select those $2m$ opposite points together with $y$ itself. All $k$ selected points are distinct, and their sum is again $ky$. The case $k=1$ simply selects $y$.

In both cases the indices stay between $0$ and $2k$ and the difference $d$ is nonzero. Thus the precise answer isNo deletion of diagonal solutions and no multidimensional density theorem is needed. The averaging point is allowed to be one of the selected points, as it is in the odd case.

Use the uniform probability measure on the Boolean hypercube. The influence of a variable is the flip probabilityThe polynomial defining $f$ is interpreted over ${\mathbb{F}}_2$. Flipping the first coordinate adds $x_2+\cdots +x_n$ modulo two. This nonempty parity is balanced for $n\ge 2$, so

An explicit Tribes function works for every $n\ge 2$. Choose the largest integer $w\ge 1$ with $w{2}^w\le n$, let $m=\lfloor 2^w\log 2\rfloor$, and take the OR of $m$ disjoint ANDs of $w$ coordinates. Ignore the unused coordinates. Its zero probability is $(1-2^{-w}{)}^m$, between $1/4$ and $3/4$, and a used coordinate has influenceHere $n<2^{w+1}(w+1)$ by maximality. For the balance claim, $w=1$ gives probability $1/2$; for $w\ge 2$, $m\ge 2^w\log 2-1$ gives zero probability at most $e^{-\log 2+2^{-w}}<3/4$, while $(1-1/q{)}^q\ge 1/4$ for $q=2^w\ge 2$ gives a lower bound $(1/4{)}^{\log 2}>1/4$. Only the example was requested, but these checks fix its parameters unambiguously.

For the lower bound we prove the required consequence of Beckner's inequality with constants. Write the Fourier-Walsh transform as $f={\sum }_S\hat{f}(S){\chi }_S$, where ${\chi }_S(x)=(-1{)}^{{\sum }_{i\in S}{x}_i}$ and $\hat{f}(S)=\mathbb{E}(f{\chi }_S)$. The discrete derivative of a Boolean function is $D_{i}f=(f-f(\cdot +e_i))/2$. Since $f$ takes values zero and one, $D_{i}f$ takes values $0,\pm 1/2$. Consequently Parseval's identity givesThe factor four is required for the printed $0/1$ convention. Also $V:=\mathrm{Var}(f)={\sum }_{S\ne \varnothing }|\hat{f}(S){|}^2\ge 3/16$ under the balance hypothesis.

The true Beckner's inequality states $\Vert T_{\rho }h{\Vert }_q\le \Vert h{\Vert }_p$ for $1<p\le q<\infty$, $0\le \rho \le \sqrt{(p-1)/(q-1)}$, with $T_{\rho }h={\sum }_S{\rho }^{|S|}\hat{h}(S){\chi }_S$. Apply it with $p=3/2$, $q=2$, $\rho =1/\sqrt{2}$ to $h_i={\chi }_{\{i\}}{D}_{i}f$, a function independent of coordinate $i$. Its nonzero values still have magnitude $1/2$. We obtainLet $a={\max }_i{I}_i(f)>0$. For an integer $\ell \ge 1$, the low-degree Fourier weight satisfiesFor the high-degree part the total influence identity givesTogether these imply $4V\le na(2^{\ell -1}{a}^{1/3}+1/(\ell +1))$.

Suppose, seeking a contradiction, that $a<\log n/(100n)$, with natural logarithms. Then $a<1/(100e)$ and $\ell =\lfloor \log (1/a)/(6\log 2)\rfloor \ge 1$. Hence $2^{\ell -1}{a}^{1/3}\le a^{1/6}/2$. Put $y=\log n$. The first term on the right is bounded bythe middle expression is maximized at $y=7$. Moreover $\log (1/a)\ge y/2$, since $y\le 100e^{y/2}$. ThusWe would have $4V<1/10$, contradicting $4V\ge 3/4$. ThereforeThis derives the stated Kahn-Kalai-Linial theorem bound from the actual noise operator on the Boolean hypercube inequality, rather than using the desired conclusion as an input.