Expansion of trivariate polynomials using proximity

Basic Information

• Paper ID: 2510.12191
• Title: Expansion of trivariate polynomials using proximity
• Author: Orit E. Raz (Ben-Gurion University of the Negev)
• Classification: math.CO (Combinatorics)
• Publication Date: October 15, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.12191

Abstract

This paper extends the proximity technique of Solymosi and Zahl to the setting of trivariate polynomials. The main result is: for $f(x,y,z)=(x-y)^2+(\phi(x)-z)^2$, where $\phi(x)\in \mathbb{R}[x]$ has degree at least 3, for any finite sets $A,B,C\subset \mathbb{R}$ each of size $n$, we have $|f(A,B,C)|=\Omega(n^{5/3-\varepsilon})$ for any arbitrarily small $\varepsilon>0$. This improves the previously established exponent of $3/2$ by Raz, Sharir, and De Zeeuw. To the author's knowledge, this is the first result for trivariate polynomials that surpasses the $\Omega(n^{3/2})$ expansion bound.

Research Background and Motivation

Problem Background

1. Polynomial expansion problem: Study the size of the image set of multivariate real polynomials $f$ on Cartesian products of finite sets. This class of problems originates from Elekes's unified study of counting problems in combinatorial geometry involving distances, slopes, and collinearity.
2. Elekes-Rónyai theorem: For bivariate polynomials $f(x,y)$, unless $f$ has special form ($f(x,y)=h(p(x)+q(y))$ or $f(x,y)=h(p(x)q(y))$), we have $|f(A,B)|=\omega(n)$.
3. Challenges in the trivariate case: Although Raz, Sharir, and De Zeeuw have generalized results to trivariate and higher-dimensional cases, the expansion bounds remain at $\Omega(n^{3/2})$, unable to break through this bottleneck.

Research Motivation

1. Methodological innovation: The proximity method successfully improved the bound from $\Omega(n^{4/3})$ to $\Omega(n^{3/2})$ in the bivariate case, but how to extend it to the trivariate case is not obvious.
2. Theoretical breakthrough: Seeking the first trivariate polynomial result that surpasses the $\Omega(n^{3/2})$ bound, opening new research directions in this field.
3. Technical challenges: The trivariate case avoids the loss caused by Cauchy-Schwarz inequality in the bivariate case, but how to leverage the proximity technique to obtain stronger results still requires new insights.

Core Contributions

1. First breakthrough in trivariate polynomial expansion bounds: Proves that the expansion bound for a specific family of trivariate polynomials is $\Omega(n^{5/3-\varepsilon})$, surpassing the previous $\Omega(n^{3/2})$ limit.
2. Trivariate extension of proximity technique: Successfully generalizes the Solymosi-Zahl proximity method to the trivariate polynomial setting, resolving the application challenges of this technique in higher dimensions.
3. New analytical framework: Provides a refined analysis method for reducing trivariate polynomial expansion problems to planar point-curve incidence problems.
4. Universality of theoretical methods: The proposed method is general and can be extended to other trivariate polynomial families, laying the foundation for future research.

Detailed Methodology

Problem Definition

Given a trivariate polynomial $f(x,y,z)=(x-y)^2+(\phi(x)-z)^2$, where $\phi(x)$ is a univariate real polynomial of degree at least 3, and three finite sets of real numbers $A,B,C$ each of size $n$, the goal is to establish a lower bound for the size of the image set $f(A,B,C)=\{f(a,b,c)|a\in A, b\in B, c\in C\}$.

Core Technical Framework

1. Proximity Partitioning Strategy

• Set $D:=f(A,B,C)$ and define parameter $t=n^{3/2}/(s|D|^{1/2})$, where $s>0$ is a sufficiently large constant
• Partition each set $A,B,C$ into $t$ consecutive segments, each containing at most $\lceil n/t\rceil$ elements
• Define proximity relation: $a\sim a'$ if and only if $a\neq a'$ and there exists a partition segment containing both $a,a'$

2. Key Set Construction

Define the set $Q$ as the collection of quadruple pairs satisfying: $Q := \{((a,b,c),(a',b',c'))\in (A\times B\times C)^2 | f(a,b,c)=f(a',b',c'), a\sim a', b\sim b', c\sim c'\}$

3. Two-Directional Bounding Strategy

Lower Bound Estimate (Proposition 6):

• For each $d\in D$, define $G_d:=\{(a,b,c)\in A\times B\times C | f(a,b,c)=d\}$
• Identify the set of "important" values $D':=\{d\in D | |G_d|\geq n^3/(10|D|)\}$
• Use combinatorial counting arguments to show $|Q|=\Omega(sn^3)$

Upper Bound Estimate (Proposition 7):

• Reduce the problem to planar point-curve incidence problems
• For each pair $((b,c),(b',c'))\in (B\times C)^2$, construct the planar curve $\gamma_{b,c,b',c'}$: $f(x,b,c)=f(x',b',c')$
• Apply the Sharir-Zahl incidence bound theorem to obtain $|Q|=O_\varepsilon((s^2n|D|)^{9/8+\varepsilon})+4\deg(\phi)n^3$

Technical Innovations

1. Refined partitioning technique: Through careful choice of parameter $t$, balances the effects of proximity constraints and incidence bound applications.
2. Symmetry analysis of curve families: Utilizes Lemma 4 (Pach-De Zeeuw) on bounds for algebraic curve symmetries to control the number of curves with multiple parameter representations.
3. Geometric rigidity arguments: Through geometric analysis in Lemma 5, proves that when multiple parameters correspond to the same curve, geometric rigidity constraints necessarily exist.

Experimental Setup

This is a pure theoretical mathematics paper with no numerical experiments. All results are obtained through rigorous mathematical proofs.

Main Theorems and Proof Structure

Main Theorem (Theorem 2)

Theorem 2: Let $f(x,y,z)=(x-y)^2+(\phi(x)-z)^2$, where $\phi(x)$ is a univariate real polynomial of degree at least 3. Then for any $\varepsilon>0$ and any finite sets $A,B,C\subset\mathbb{R}$ of size $n$, we have $|f(A,B,C)|=\Omega(n^{5/3-\varepsilon})$ where the implicit constant depends on $\deg\phi$ and $\varepsilon$.

Core Proof Steps

1. Establishing two-directional inequalities:
   • Lower bound: $|Q|\geq \Omega(sn^3)$ (Proposition 6)
   • Upper bound: $|Q|\leq O_\varepsilon((s^2n|D|)^{9/8+\varepsilon})+4\deg(\phi)n^3$ (Proposition 7)
2. Parameter optimization: Choose $s>8\deg(\phi)$ so that higher-order terms are controlled by the main term.
3. Final derivation: $sn^3 \leq O_\varepsilon((s^2n|D|)^{9/8+\varepsilon}) + 4\deg(\phi)n^3$
   After simplification, we obtain $|D|=\Omega_\varepsilon(n^{5/3-\varepsilon'})$.

Related Work

Historical Development

1. Elekes problem (1997): Proposes the basic framework for bivariate polynomial expansion problems.
2. Elekes-Rónyai theorem (2000): Establishes dichotomy results for the bivariate case.
3. Raz-Sharir-Solymosi method (2016): Introduces the point-curve incidence method, achieving $\Omega(n^{4/3})$ bound.
4. Solymosi-Zahl proximity technique (2024): Achieves $\Omega(n^{3/2})$ bound in the bivariate case.
5. Multivariate generalizations: Raz-Sharir-De Zeeuw and Raz-Shem Tov extend results to $k\geq 3$ variables, but bounds remain $\Omega(n^{3/2})$.

Position of This Paper

This paper is the first to break through the $\Omega(n^{3/2})$ bound in the trivariate case, opening new directions for the field.

Conclusions and Discussion

Main Conclusions

1. Successfully extends the proximity technique to trivariate polynomials, achieving an $\Omega(n^{5/3-\varepsilon})$ expansion bound.
2. Proves that specific trivariate polynomial families can indeed surpass previously established general bounds.
3. Provides a new methodological framework for handling high-dimensional polynomial expansion problems.

Limitations

1. Restriction on polynomial families: Results apply only to polynomials of the form $(x-y)^2+(\phi(x)-z)^2$.
2. Degree requirement: Requires the restriction $\deg(\phi)\geq 3$.
3. Constant dependence: The implicit constant depends on $\varepsilon$ and $\deg(\phi)$, which may be large.

Future Directions

1. Extending polynomial families: Determine broader subfamilies of trivariate polynomials for which the method remains applicable.
2. Optimality of bounds: Determine whether $\Omega(n^{5/3-\varepsilon})$ is optimal or whether stronger bounds exist.
3. Higher-dimensional generalizations: Extend the technique to quaternary and higher-dimensional polynomials.
4. Application exploration: Seek concrete applications in combinatorial and discrete geometry.

In-Depth Evaluation

Strengths

1. Theoretical breakthrough: First to break through the long-standing $\Omega(n^{3/2})$ bound in trivariate polynomial expansion problems, with significant theoretical importance.
2. Methodological innovation: Cleverly adapts the proximity technique to the trivariate case, resolving difficulties in high-dimensional generalizations of this technique.
3. Technical rigor: Clear proof structure with precise technical details, particularly in handling curve family symmetries and geometric rigidity.
4. Mathematical depth: Synthesizes deep results from multiple mathematical branches including algebraic geometry, combinatorial geometry, and incidence theory.

Weaknesses

1. Limited applicability: Results apply only to trivariate polynomials of specific form, with limited generality.
2. Tightness of bounds unknown: Unclear whether $\Omega(n^{5/3-\varepsilon})$ is optimal; upper bound analysis may have room for improvement.
3. Lack of constructiveness: Proofs are primarily existential without providing concrete constructions achieving the lower bound.
4. Computational complexity: Although theoretical, the involved constants may be large in practical computation.

Impact

1. Field advancement: Opens new directions for multivariate polynomial expansion theory, likely to inspire subsequent research.
2. Methodological value: High-dimensional extension of proximity technique provides new analytical tools for related problems.
3. Theoretical completeness: Fills important gaps in trivariate polynomial expansion theory.

Applicable Scenarios

1. Theoretical research: Provides new insights for researchers studying multivariate polynomial expansion problems.
2. Combinatorial geometry: Potential applications in distance sets, incidence problems, and other combinatorial geometry research.
3. Algorithm analysis: Provides theoretical foundations for complexity analysis of related algorithms.

References

The paper cites important literature in the field, including:

• Elekes's pioneering work and the Elekes-Rónyai theorem
• Raz-Sharir-Solymosi's point-curve incidence method
• Solymosi-Zahl's proximity technique
• Sharir-Zahl's incidence bound theorem
• Pach-De Zeeuw's results on algebraic curve symmetries

These citations reflect the author's deep understanding of the field's development and skillful command of relevant techniques.