MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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). – Ben Green Mar 8 '13 at 7:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.