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.

  • 2
    $\begingroup$ 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. $\endgroup$
    – Wojowu
    Aug 20, 2021 at 12:40
  • 1
    $\begingroup$ @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.) $\endgroup$
    – Asaf Karagila
    Aug 20, 2021 at 15:36
  • $\begingroup$ @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. $\endgroup$
    – Random
    Aug 20, 2021 at 15:48
  • $\begingroup$ 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. $\endgroup$
    – Wojowu
    Aug 20, 2021 at 15:52


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.