# Infinitary Ruzsa triangle inequality without Choice

If $$X, Y$$ are subsets of an abelian group, we denote $$X - Y = \left\{ x - y \ \lvert \ x \in X, \ y \in Y \right\}$$.

Question: Let $$A, B, C$$ be non-empty subsets of an abelian group $$G$$. Is the inequality $$\lvert A \rvert \lvert B - C \rvert \leq \lvert A - B \rvert \lvert A - C \rvert$$ true without assuming the Axiom of Choice?

The Ruzsa triangle inequality states that for all finite subsets $$A, B, C$$ of some abelian group, the inequality $$\lvert A \rvert \lvert B - C \rvert \leq \lvert A - B \rvert \lvert A - C \rvert$$ holds. The proof, as given in the linked Wikipedia article, is as follows: for each element $$x \in B - C$$, arbitrarily choose $$b(x) \in B, \ c(x) \in C$$ such that $$b(x) - c(x) = x$$. Now, the function $$f : A \times \left( B - C \right) \to \left( A - B \right) \times \left( A - C \right)$$ which is defined by $$f(a, x) = \left( a - b(x), a - c(x) \right)$$ is injective, as $$\left( a - c(x) \right) - \left( a - b(x) \right) = b(x) - c(x)$$, and so we can recover $$b(x) - c(x) = x$$, which lets us recover $$b(x)$$, which lets us recover $$a$$.

If we try to do this for the case where $$A, B, C$$ are infinite, then when trying to choose $$b(x), c(x)$$ we need to use the Axiom of Choice, and so I wondered if this is possible to do without Choice?

By the way, assuming the axiom of Choice the infinite case has an easy proof, because if either $$B$$ or $$C$$ are infinite, then $$\max \left( \lvert B \rvert, \lvert C \rvert \right) = \lvert B \times C \rvert \geq \lvert B - C \rvert \geq \max \left( \lvert B \rvert, \lvert C \rvert \right)$$ and from here it's easy to finish, but of course this doesn't work well without Choice.

• I suspect the inequality may fail. It is conceivable to me that $B-C$ might have cardinality incomparable with $B\times C$ - we have an obvious surjection $B\times C\to B-C$, but in general surjection one way doesn't necessarily imply there is an injection the other way. If this can occur in groups, then taking $A$ a singleton gives a counterexample. Aug 20, 2021 at 12:40
• @Wojowu: Well, yes, you'd expect that. But note that $C\times(B-C)$ can be mapped onto $B$ by $(c,b-y)\mapsto (b-y)+c$ whose range includes $B$, at least; and likewise $B\times(B-C)$ can be mapped onto $C$ by $(b,d-c)\mapsto -((d-c)-b)$ whose range contains $C$. So you need to have a more intricate relationship of surjections between the sets, and you need to be able to take a surjection and code it into the group addition as well, which is not obvious. (Although having a boolean group where $x=-x$ might be useful for simplifying things.) Aug 20, 2021 at 15:36
• @Wojowu Your comment shows that the question is in fact equivalent to the case where $A$ is a singleton, since as you said this case (if true) gives us an injection $B - C \to B \times C$ which lets us finish the proof as I described above. Aug 20, 2021 at 15:48
• What your argument requires is not just an arbitrary injection $B-C\to B\times C$, but rather a section of this projection. The two are far from equivalent. Aug 20, 2021 at 15:52