Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
2  
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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.