A combinatorial problem on polynomials
In 1973 G. A. Freiman described the structure of \(n\)-element sets \(A\subset \mathbb{R}\) for which \(| A+A|\leq C_n\): He proved that \(A\) must be contained in a ``generalized arithmetic progression. Here the author studies polynomials of two real variables which behave like \(x+y\), i.e. which can take only few distinct values when \(x\) and \(y\) range independently over appropriate finite subsets of \(\mathbb{R}\). Like \(x+y\), \(x\cdot y\) is such a ``restricted polynomial: it takes only \(2n-1\) distinct values when \(x\) and \(y\) are from a geometric progression. The author conjectures that these two cases are typical in the sense that if \(P\) is restricted, then there are polynomials \(f\), \(g\), \(h\) such that either \(P(x,y)= f(g(x)+ h(y))\) or \(P(x,y)= f(g(x)\cdot h(y))\). Using methods from combinatorial geometry he proves two special cases. In a note he adds that the conjecture has been proved in a forthcoming paper in the Journal of Combinatorial Theory.
- Some combinatorial questions about polynomial mappings
- A combinatorial problem on polynomials and rational functions
- The Szemerédi-Trotter theorem in the complex plane
- Restricted sums in a field
- scientific article; zbMATH DE number 16456 (Why is no real title available?)
- Products of differences over arbitrary finite fields
- An Extension of the Perplexing Polynomial Puzzle
- The structure of sets with few sums along a graph
This page was built for publication: A combinatorial problem on polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1387848)
