On some arithmetic conditions of recurrent sequences modulo prime p

Technical Summary: On some arithmetic conditions of recurrent sequences modulo prime $p$

Problem Statement
The paper investigates the arithmetic properties of the $K$-Fibonacci sequence modulo a prime $p$. Specifically, it focuses on estimating the cardinalities of the sum set $|F_p + F_p|$ and the product set $|F_p \cdot F_p|$, where $F_p$ denotes the set of elements generated by the $K$-Fibonacci recurrence relation modulo $p$. The $K$-Fibonacci sequence is defined by $F_{n+2} = K F_n + F_{n+1}$ with initial conditions $F_0=0, F_1=1$, where $K \in \mathbb{F}_p^*$. This generalizes the classical Fibonacci sequence ($K=1$) and the Pell number sequence ($K=2$). The work addresses the "doubling" problem in additive and multiplicative combinatorics, seeking lower bounds for the size of these sets relative to the size of the original set $|F_p|$.

Methodology
The authors employ a method for estimating the doubling constant of $m$-dimensional recurrent sets in $\mathbb{F}_p$. The core approach involves:

1. Representation of Recurrent Sequences: The sequence elements are expressed in terms of the roots of the characteristic polynomial. For the $K$-Fibonacci sequence, the authors decompose the set $F_p$ into the union of two recurrent subsequences ($F'_p$ and $F''_p$) corresponding to even and odd indices. These subsequences are represented as linear combinations of powers of elements in a multiplicative subgroup $G \subset \mathbb{F}_{p^s}^*$, specifically in the form $X_n = \sum \alpha_i x^{k_i}$ where $x \in G$.
2. Polynomial Doubling and Irreducibility: The problem is generalized to the cardinality of the set $P(X, X) = \{P(X, Y) \mid X, Y \in X\}$ for a polynomial $P$. To bound the number of solutions to $P(X, Y) = r$, the authors transform the problem into finding solutions to a polynomial equation $Q_r(x, y) = 0$ within the subgroup $G$.
3. Application of Subgroup Bounds: The authors utilize existing bounds on the number of solutions of polynomial equations in subgroups (citing Theorem 2 from [5] and Theorem 1.2 from [4]). These bounds depend on the degree of the polynomial and the size of the subgroup, provided the polynomial is absolutely irreducible and satisfies specific non-degeneracy conditions.
4. Newton Polygons for Irreducibility: A critical step is proving the absolute irreducibility of the transformed polynomials $Q_r(x, y)$. The authors use Newton polygons to analyze the structure of these polynomials. They demonstrate that for specific polynomials related to addition ($x+y$) and multiplication ($xy$), the Newton polygons cannot be decomposed into the Minkowski sum of smaller polygons (except in degenerate cases), thereby proving irreducibility.

Key Contributions and Results
The primary contribution is the establishment of lower bounds for the cardinality of the sum and product sets of the $K$-Fibonacci sequence modulo $p$.

• Main Theorem (Theorem 1): Under the condition that $|F_p| < \frac{1}{6}p^{3/4}$, the paper proves that there exists an absolute constant $C$ such that:
  $$|F_p + F_p| > C|F_p|^{4/3}$$
  $$|F_p \cdot F_p| > C|F_p|^{4/3}$$
• Technical Lemmas: The paper provides specific proofs of irreducibility for polynomials $P_1(x, y) = \alpha x^2y + \gamma xy^2 - rxy + \delta x + \beta y$ and $P_2(x, y)$ (related to the product case) using Newton polygon analysis. These lemmas ensure the applicability of the subgroup solution bounds to the specific structure of the $K$-Fibonacci sequence.
• Generalization: The methodology is presented as applicable to a broader class of $m$-dimensional recurrent sequences modulo $p$, contingent on the irreducibility of the associated polynomial series.

Significance and Claims
The paper claims to present a method for estimating the doubling constant of $m$-dimensional recurrent sets. By applying this method to the $K$-Fibonacci sequence, the authors establish that these sets exhibit significant growth under addition and multiplication, satisfying bounds similar to those found in sum-product problems for general sets. The work connects the arithmetic of linear recurrence sequences with additive combinatorics, specifically utilizing the structure of the underlying multiplicative subgroup generated by the characteristic roots. The authors note that the method relies on proving the irreducibility of the associated polynomials, a task they explicitly complete for the $K$-Fibonacci case using Newton polygons. The results are framed as theoretical estimates within the domain of arithmetic number theory, without proposing new applications or experimental validations.