Some Generalizations of Totient Function with Elementary Symmetric Sums

Technical Summary: Some Generalizations of Totient Function with Elementary Symmetric Sums

Problem Statement
The paper addresses the generalization of the Euler totient function within the context of elementary symmetric sums. While recent work by Tóth [Tót22] established a $k$-dimensional generalized totient function based on the first ($e_1$) and $k$-th ($e_k$) elementary symmetric sums, and Csizmadia and Tóth [CT25] extended this to arbitrary sets of polynomials, there remained a need to analyze intermediate symmetric sums, specifically the second elementary symmetric sum $e_2(x) = \sum_{1 \le i < j \le k} x_i x_j$.

The core problem involves defining and deriving explicit product formulas for two distinct counting functions over the ring $\mathbb{Z}_n^k$:

1. $\phi_J(n)$: The number of tuples $(x_1, \dots, x_k)$ such that the greatest common divisor of the set of symmetric sums $\{e_j\}_{j \in J}$ and $n$ is 1 (i.e., $\gcd(e_{j_1}, \dots, e_{j_m}, n) = 1$).
2. $\varphi_J(n)$: The number of tuples where each individual symmetric sum is coprime to $n$ (i.e., $\gcd(e_j, n) = 1$ for all $j \in J$).

The authors specifically focus on sets $J$ involving the second symmetric sum, such as $\{2\}$, $\{1, 2\}$, $\{2, k\}$, and $\{1, 2, k\}$.

Methodology
The methodology relies on the multiplicative properties of these functions and the enumeration of solutions to polynomial congruences over finite fields.

1. Reduction to Finite Fields: Following the framework of Csizmadia and Tóth [CT25], the authors utilize the fact that $\phi_J(n)$ is multiplicative. The problem is reduced to calculating $N_J(p)$, the number of common zeros of the polynomials in $J$ over the finite field $\mathbb{F}_p$. The product formula is then given by $\phi_J(n) = n^k \prod_{p|n} (1 - N_J(p)/p^k)$.
2. Quadratic Form Analysis: For the set $J=\{2\}$, the condition $e_2(x) \equiv 0 \pmod p$ represents a quadratic form. The authors analyze the associated symmetric matrix $A$ to determine if the form is degenerate or non-degenerate. They apply standard results (Lemma 2.0.3, citing Lidl and Niederreiter [LN97]) regarding the number of solutions to non-degenerate quadratic equations over $\mathbb{F}_p$, distinguishing cases based on the parity of $k$ and the characteristic $p$.
3. Inclusion-Exclusion Principle: To handle sets involving multiple symmetric sums (e.g., $J=\{1, 2\}$ or $J=\{2, k\}$), the authors employ the inclusion-exclusion principle. Theorem 3.0.1 establishes a relationship between $\phi_J$ and $\varphi_J$ via inclusion-exclusion over subsets of $J$. Theorem 2.0.4 provides a recursive method to calculate $N_J(p)$ when $J$ includes $e_k$ by relating it to solutions where specific variables are zero.
4. Roots of Unity Filters: For the case $p=2$, where standard quadratic form theory over odd primes does not apply directly, the authors utilize roots of unity filters (specifically with $\omega_4 = i$) to count solutions based on the number of non-zero components in the vector.

Key Contributions and Results

• Explicit Product Formulas: The paper derives explicit product formulas for $\phi_J(n)$ and $\varphi_J(n)$ for several specific sets $J$:

  • $\phi_{\{2\}}(n)$: Derived in Theorem 2.0.1, providing the count of solutions to $e_2(x) \equiv 0 \pmod p$ for both odd and even $k$, and for $p=2$.
  • $\phi_{\{1, 2\}}(n)$: Derived in Theorem 2.0.2, handling the simultaneous vanishing of $e_1$ and $e_2$.
  • $\phi_{\{2, k\}}(n)$ and $\phi_{\{1, 2, k\}}(n)$: Derived in Corollaries 2.0.5 and 2.0.6 using the recursive inclusion-exclusion method.
  • $\varphi_{\{1, 2\}}(n)$: Derived in Theorem 3.0.3 by combining the results for $\phi_{\{1\}}$, $\phi_{\{2\}}$, and $\phi_{\{1, 2\}}$ via the inclusion-exclusion relation.

• Menon-Type Identities: Theorem 3.0.2 establishes a Menon-type identity for the function $\varphi_J(n)$ when $1 \in J$. It relates the sum of a function $f$ over the greatest common divisor of the linear sum and $n$ to the totient value $\varphi_J(n)$, generalizing previous results by Tóth [Tót21].

• Restricted Linear Congruences: The paper applies these generalized totient functions to count solutions of restricted linear congruences of the form $\sum a_i x_i \equiv b \pmod n$ subject to $\gcd(e_j(x), n) = 1$. Theorem 4.0.2 shows that for $\gcd(b, n)=1$, the number of solutions is given by $g_k(n) = \varphi_{F'}(n) / \phi(n)$, where $F'$ includes the linear form and the symmetric constraints. An explicit solution count is provided for the case where the constraint is $\gcd(e_2(x), n)=1$.

Significance and Claims
The authors claim to extend the framework of generalized totient functions beyond the previously studied sets $\{e_1, e_k\}$ to include the second elementary symmetric sum $e_2$. The significance lies in:

1. Structural Links: Revealing deeper connections between polynomial zeros over finite fields, restricted linear congruences, and generalized Euler totients.
2. Divisibility Properties: Establishing that the new $e_2$-based totients share divisibility properties with the standard Euler totient function $\phi(n)$, similar to Tóth's earlier findings for $\{e_1, e_k\}$.
3. Explicit Computability: Providing concrete, computable product formulas for cases involving quadratic forms ($e_2$), which were previously open or less explored.

The paper concludes modestly by noting that while explicit forms are derived for $e_2$-based generalizations, the analysis for higher-order elementary symmetric sums ($e_l$ for $l > 2$) remains an open problem. The authors also provide a method using Lucas' theorem to count solutions for $e_l(x) \equiv 0 \pmod 2$ for general $l$, though explicit product forms for general $l$ are not fully developed in this work.