The polynomial Freiman-Ruzsa conjecture states that there exists $k > 0$, such that for all $\epsilon > 0$, and for all large $n$ and all functions $ f: \mathbb{F}_2^n \mapsto\mathbb{F}_2^n$, the following holds. If

$$Pr_{x, x' \in \mathbb{F}_2^n} [f(x) + f(x') = f(x+x')] \geq \epsilon \;,$$ then there is a matrix $M \in \mathbb{F}_2^{n \times n}$ such that

$$Pr_{x \in \mathbb{F}_2^n} [ f(x) = M x] \geq \epsilon^k]\;.$$

My question is whether we can prove this conjecture for the special case when $f$ is known to be a bijection.

  • 3
    $\begingroup$ It seems unlikely to me that the bijection assumption would help. If f is an arbitrary function then, provided f is not "really far" from a bijection I'd expect that some modification f'(x) = f(x) + eps(x) with eps varying in a small set would make f' pretty close to a bijection (perhaps use Hall's marriage theorem or something). PFR for f and for f' are basically the same problem. Being a bijection is not a property that is useful in connection with several of the existing techniques in the area, particularly Fourier analysis (cf. the work of Sanders). $\endgroup$ – Ben Green Mar 8 '13 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.