Generic solutions to symmetric linear equations
Abstract
In 1993, Ruzsa showed that for every k ≥ 2, there exists a constant C such that every subset A ⊆ [N] of size at least C N1/k contains 2k distinct elements a1, …, ak, b1, …, bk ∈ A such that a1 + ⋯ + ak = b1 + ⋯ + bk. We strengthen this result by proving that the elements a1, …, ak, b1, …, bk can be chosen to have the additional property that {a1, …, ak, b1, …, bk} has 22k−1 distinct subset sums, with the only coincidence being that {a1, …, ak} and {b1, …, bk} have the same sum. Our proof also applies to any finite Abelian group of odd order N, and it provides a corresponding supersaturation result: that whenever |A| ≥ CN1/k, there are at least Ω(|A|2k/N) choices for a1, …, ak, b1, …, bk ∈ A satisfying these properties. We prove a slightly weaker statement for Abelian groups of even order. We also apply our methods to the vector space setting and prove the following 𝔽q-analogue of the Bondy-Simonovits Theorem on the extremal number of even cycles in graphs: Any rank-n, simple, 𝔽q-representable matroid with no circuit of size exactly 2k has size at most C qn/k for some constant C depending only on q and k. When q=2, this is best possible up to the constant C for all k ≥ 2. Our methods also apply to the original graph setting and give a new proof of the Bondy-Simonovits Theorem and its supersaturation version.
Related
- Long-Time Behavior towards Generic Riemann Solutions for Radiative Euler Equations
- Asymptotic behavior of generic Riemann solutions to one-dimensional full compressible Navier-Stokes-Poisson equations
- On the non-uniqueness of solutions of the axi-symmetric swirl-free Navier-Stokes equations, I
- A sufficient condition for the existence of solutions of singular linear-quadratic vector equations
- Dense orbits for scale-invariant rotationally symmetric solutions of the 2D Euler equations
BibTeX
@misc{frederickson2026generic,
title = {{Generic solutions to symmetric linear equations}},
author = {Bryce Frederickson and Liana Yepremyan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02177},
eprint = {2610.02177},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02177},
}
RIS
TY - UNPB
TI - Generic solutions to symmetric linear equations
AU - Bryce Frederickson
AU - Liana Yepremyan
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02177
UR - https://arxiv.org/abs/2610.02177
AB - In 1993, Ruzsa showed that for every k ≥ 2, there exists a constant C such that every subset A ⊆ [N] of size at least C N^1/k contains 2k distinct elements a_1, …, a_k, b_1, …, b_k ∈ A such that a_1 + ⋯ + a_k = b_1 + ⋯ + b_k. We strengthen this result by proving that the elements a_1, …, a_k, b_1, …, b_k can be chosen to have the additional property that {a_1, …, a_k, b_1, …, b_k} has 2^2k−1 distinct subset sums, with the only coincidence being that {a_1, …, a_k} and {b_1, …, b_k} have the same sum. Our proof also applies to any finite Abelian group of odd order N, and it provides a corresponding supersaturation result: that whenever |A| ≥ CN^1/k, there are at least Ω(|A|^2k/N) choices for a_1, …, a_k, b_1, …, b_k ∈ A satisfying these properties. We prove a slightly weaker statement for Abelian groups of even order. We also apply our methods to the vector space setting and prove the following 𝔽_q-analogue of the Bondy-Simonovits Theorem on the extremal number of even cycles in graphs: Any rank-n, simple, 𝔽_q-representable matroid with no circuit of size exactly 2k has size at most C q^n/k for some constant C depending only on q and k. When q=2, this is best possible up to the constant C for all k ≥ 2. Our methods also apply to the original graph setting and give a new proof of the Bondy-Simonovits Theorem and its supersaturation version.
ER -