Some Generalizations of Totient Function with Elementary Symmetric Sums

Basic Information

• Paper ID: 2511.19502
• Title: Some Generalizations of Totient Function with Elementary Symmetric Sums
• Authors: Udvas Acharjee, N. Uday Kiran
• Affiliation: Department of Mathematics and Computer Science, Sri Sathya Sai Institute of Higher Learning, Puttaparthi, India
• Classification: math.NT (Number Theory)
• Publication Date: November 26, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2511.19502v1

Abstract

This paper generalizes certain totient functions using elementary symmetric polynomials and derives explicit product forms for totient functions involving the second elementary symmetric sum. This work extends research by Tóth (2022) in The Ramanujan Journal, which generalized the totient function using the first and k-th elementary symmetric polynomials. The authors provide observations regarding the behavior of totient functions with respect to arbitrary j-th elementary symmetric polynomials and outline a method for solving restricted linear congruence problems with quadratic form greatest common divisor constraints. Most importantly, the paper establishes equivalence between obtaining product forms of generalized totient functions, computing zeros of specific polynomials over finite fields, and solving a broad class of restricted linear congruence problems.

Research Background and Motivation

Problem Background

1. Generalizations of the Classical Euler Totient Function: The Euler totient function φ(n) counts positive integers less than n that are coprime to n. Since Menon's polynomial-based generalization in 1967, multiple generalizations have emerged, including the Schemmel totient function and Nagell totient function.
2. Development of Multivariate Generalizations: Stevens (1971) proposed multivariate generalizations encompassing the Jordan totient function. Recently, Csizmazia and Tóth (2025) extended this further to multivariate polynomial systems.
3. Application of Elementary Symmetric Polynomials: Tóth (2022) generalized the totient function using the 1st and k-th elementary symmetric sums, obtaining elegant product formulas.

Research Motivation

1. Natural Mathematical Extension: Tóth's work employed e₁ and eₖ (the 1st and k-th elementary symmetric sums), naturally raising research questions about the 2nd elementary symmetric sum e₂ and other symmetric sums.
2. Unification of Three Problems: The authors discover profound connections between product forms of generalized totient functions, polynomial zero counting over finite fields, and restricted linear congruence problems, providing a new perspective for unified treatment of these seemingly distinct problems.
3. Practical Application Value: Restricted linear congruence problems have important applications in cryptography and coding theory, while totient functions hold fundamental status in number theory.

Limitations of Existing Methods

1. Explicit product formulas for the case of the 2nd elementary symmetric sum e₂ are lacking
2. A unified framework for handling different types of elementary symmetric sums is absent
3. The connection between restricted linear congruence problems and totient functions has not been fully revealed

Core Contributions

1. Establishing Relationships Between Two Types of Totient Functions: Proves the inclusion-exclusion principle relationship between φ_F(n) and ϕ_F(n) (Theorem 2.0.1), enabling the product form of one function to be derived from the other.
2. Deriving Explicit Formulas for the Second Elementary Symmetric Sum:
   • Provides explicit formula for N_k(e₂, p) (Theorem 3.0.2)
   • Derives product form for φ_{e₂}(n) (Theorem 3.0.3)
   • Provides formulas for joint cases involving e₁ and e₂ (Theorems 3.0.4-3.0.11)
3. Establishing Equivalence of Three Problems: Proves equivalence relationships among:
   • Product forms of generalized totient functions
   • Zero point counting of polynomial systems over finite fields
   • Solutions to restricted linear congruence problems
4. Providing Concrete Algorithms and Examples:
   • Closed-form solutions for p=2 using generating functions and De Moivre's theorem
   • Specific examples for k=3 and k=4 variables
   • Generalization of Menon's identity to new cases (Theorem 3.0.10)
5. Extension of Theoretical Framework: Proposes recursive methods for handling arbitrary j-th elementary symmetric polynomials (Theorem 3.0.8)

Detailed Methodology

Task Definition

This paper studies two classes of generalized totient functions:

Definition 1 (φ_F function): For polynomial set F = {f₁, ..., f_m},

φ_F(n) := |{(a₁,...,aₖ) ∈ Z^k_n : gcd(f₁(a₁,...,aₖ),...,f_m(a₁,...,aₖ), n) = 1}|

Definition 2 (ϕ_F function): Requiring each polynomial value to be coprime to n,

ϕ_F(n) := |{(a₁,...,aₖ) ∈ Z^k_n : gcd(f₁(a₁,...,aₖ), n) = ··· = gcd(f_m(a₁,...,aₖ), n) = 1}|

Elementary Symmetric Polynomials:

e_j(x₁,...,xₖ) = ∑_{1≤i₁<···<i_j≤k} x_{i₁}···x_{i_j}

Core Methodological Architecture

1. Inclusion-Exclusion Principle Connecting Two Function Classes

Theorem 2.0.1: Establishes bidirectional conversion relationships between φ_F and ϕ_F:

ϕ_F(p^k) = ∑_{J⊆F} (-1)^{|J|+1} φ_J(p^k)
φ_F(p^k) = ∑_{J⊆F} (-1)^{|J|+1} ϕ_J(p^k)

Proof Strategy:

• Use N_(p) to denote the cardinality of the union of zero sets
• Apply inclusion-exclusion principle: N_(p) = ∑_{J⊆F} (-1)^{|J|+1} N_J(p)
• Substitute into product formula φ_F(p^k) = p^k(1 - N_F(p)/p^k)

2. Quadratic Form Theory for Computing Zero Points

Core Tool (Theorem 3.0.1, cited from Lidl-Niederreiter): For a non-degenerate quadratic form f, the number of solutions to f(x₁,...,xₖ) = b over F_p is:

N(b) = {
  p^{k-1} + p^{(k-1)/2}η((-1)^{(k-1)/2}bΔ),  k odd
  p^{k-1} + ν(b)p^{(k-2)/2}η((-1)^{k/2}Δ),  k even
}

where η is the quadratic character, Δ = det(f), ν(b) = -1 (b≠0), ν(0) = p-1.

Application to e₂: The second elementary symmetric sum corresponds to the symmetric matrix:

A = [0      2^{-1}  ···  2^{-1}]
    [2^{-1}  0      ···  2^{-1}]
    [  ⋮      ⋮     ⋱     ⋮   ]
    [2^{-1} 2^{-1}  ···    0  ]_{k×k}

Determinant: Δ = det(A) = (-1)^{k-1}2^{-k}(k-1)

Key Analysis:

• Non-degenerate case (Δ≠0): Direct application of quadratic form theorem
• Degenerate case (k≡1 mod p): Null space is span{(1,1,...,1)^T}, handled through dimension reduction to (k-1)×(k-1) non-degenerate matrix

3. Special Treatment for p=2

For p=2, using combinatorial methods:

• For vector v∈{0,1}^k with j ones, v^T Av = j(j-1)/2
• Equals 0 when j≡0,1 (mod 4)
• Transforms to filtered binomial coefficient sums

Generating Function Technique:

∑_{j≡0 mod 4} (k choose j) = (1/4)∑_{i=0}^3 f(ω_4^i), f(x) = (1+x)^k

Using De Moivre's theorem to obtain closed form:

N_k(e₂, 2) = (1/4)(2^{k+1} + 2(√2)^{k+1}cos(π/4 - kπ/4))

Technical Innovation Points

1. Systematic Treatment of Matrix Degeneracy: When det(A)=0, constructs k-1 linearly independent vectors for dimension reduction, transforming degenerate problems into non-degenerate ones.
2. Application of Lucas' Theorem: In Remark 3.0.1, uses Lucas' theorem to characterize binomial coefficient parity, resolving the general l-th elementary symmetric sum case for p=2.
3. Recursive Framework: Theorem 3.0.8 provides recursive formula for computing N_k(J∪{k}, p) from N_k(J,p):

N_k(J∪{k}, p) = ∑_{j=1}^k (-1)^{j+1}(k choose j)N_{k-j}(J/{k-j+1,...,k-1}, p)

4. Unification of Three Problems: Through the relationship diagram in Figure 1, establishes:
   • Product form ↔ Finite field zero point counting (via Theorems 3.0.3, etc.)
   • Totient function ↔ Restricted linear congruence (via Theorem 3.1.2)
   • φ_F ↔ ϕ_F (via Theorem 2.0.1)

Experimental Setup

Note: This is a pure mathematics theory paper without traditional experiments, but rather verification through rigorous mathematical proofs and concrete examples.

Theoretical Verification Methods

1. Special Case Verification:
   • Verification of specific formulas for k=3 (Theorem 3.0.12)
   • Verification of specific formulas for k=4 (Theorem 3.1.5)
2. Recovery of Known Results:
   • Proves that when J={1,2,...,k}, φ_J(n) = J_k(n) (Jordan totient function, Corollary 3.0.9)
   • Verifies consistency with Tóth (2022) results on e₁ and e_k
3. Consistency Checks:
   • Verification of relationships between φ_F and ϕ_F through inclusion-exclusion principle
   • Verification of recursive formula self-consistency

Concrete Example Analysis

Example 1: k=3 Case (Theorem 3.1.3)

Consider the system:

a + b + c ≡ 1 mod n
gcd(abc, n) = gcd(ab+bc+ca, n) = 1

Lemma 3.1.4: Analysis of solvability of x²+x+1≡0 (mod p)

• Discriminant is -3
• Using quadratic reciprocity: solvable when p=3 or p≡1 (mod 3)
• 1 solution when p=3, 2 solutions when p≡1 (mod 3)

Counting Strategy:

S₁ = {(a,b,c) : gcd(abc,p^k)=1}
S₂ = {(a,b,c) : a+b+c≡0 mod p}
S₃ = {(a,b,c) : ab+bc+ca≡0 mod p}

Via inclusion-exclusion: |S₁|-|S₁∩S₂|-|S₁∩S₃|+|S₁∩S₂∩S₃|

Result:

g₃(m,n) = n² ∏_{p|n} (1 - 3/p + (6-h(p))/p²)

where h(p) = 3 (p=3), p-1 (p≡1 mod 3), p+1 (p≡2 mod 3)

Example 2: k=4 Case (Theorem 3.1.5)

Consider:

a + b + c + d ≡ m mod n
gcd(abcd, n) = gcd(abc+abd+acd+bcd, n) = 1

Key Observation: Solutions have form (r₁,-r₁,r₂,-r₂) in different permutations

Counting:

• r₁=r₂=r: (p-1)/2 choices, 6 placements → 3(p-1) solutions
• r₁≠r₂: (p-1)(p-3)/8 choices, 12×2 permutations → 3(p-1)(p-3) solutions
• Total: 3(p-1)(p-2) solutions

Result:

g₄(m,n) = n³ ∏_{p|n, p≥3} (1 - 5/p + 12/p² - 13/p³)
g₄(m,2^l) = 0 (no solutions when n is even)

Experimental Results

Main Theoretical Results

1. Complete Characterization of Second Elementary Symmetric Sum

Theorem 3.0.2: For prime p>2 and k>1,

N_k(e₂, p) = {
  p^{k-1} + (p-1)p^{(k-1)/2}η((-1)^{(k-1)/2}(1-gcd(k-1,p))),  k odd
  p^{k-1} + (p-1)p^{(k-2)/2}η((-1)^{k/2+1}(k-1)),             k even
}

For p=2:

N_k(e₂, 2) = (1/4)(2^{k+1} + 2(√2)^{k+1}cos(π/4 - kπ/4))

Significance: First complete explicit formula for the e₂ case, filling a gap in Tóth's work.

2. Formulas for Joint Cases

Theorem 3.0.4: Explicit expression for N_k(e₁, e₂, p)

Theorem 3.0.11: Product form for ϕ_{1,2}(n)

ϕ_{1,2}(n) = n^k ∏_{p|n, p odd} (1 - 1/p - (p-1)/p² + (p-1)h_k(p)/p^k)
ϕ_{1,2}(2^l) = 2^{lk}(1/4 - (1/2)(√2)^k sin(kπ/4))

3. Solutions to Restricted Linear Congruences

Example 3.1.1: For gcd(m,n)=1, the number of solutions to

x₁ + ··· + x_k ≡ m mod n
gcd(e₂(x₁,...,x_k), n) = 1

is:

g_k(m,n) = ϕ_{1,2}(n)/φ(n)

Important Observations and Findings

1. Recovery of Jordan Totient Function (Corollary 3.0.9): When J={1,2,...,k}, φ_J(n) = J_k(n), verifying the correctness of the new framework.
2. Symmetry: ϕ_{i,k}(n) = ϕ_{k-i,k}(n), reflecting the intrinsic symmetry of elementary symmetric polynomials.
3. Generalization of Menon's Identity (Theorem 3.0.10): When 1∈J,

∑_{(a₁,...,a_k)∈S} f(gcd(a₁+···+a_k-1, n)) = ϕ_J(n) ∑_{d|n} (μ*f)(d)/φ(d)

4. Connection to Ramanujan Sums (Remark 3.1.1):

C̃_k(m,n) = g_k(1,n)c(m,n)

where c(m,n) is the Ramanujan sum, revealing potential connections to signal processing and coding theory.

Verification of Method Effectiveness

1. Consistency with Known Results:
   • Recovers classical Euler totient function when F={x}
   • Consistent with Tóth (2022) results when F={e₁,e_k}
2. Internal Consistency:
   • Two directions of Theorem 2.0.1 are inverse operations
   • Recursive formula (Theorem 3.0.8) is correct at boundary cases
3. Computational Feasibility:
   • Explicit computable formulas for small k values (k=3,4)
   • Closed form for p=2 case via generating functions

Related Work

Historical Development Timeline

1. Classical Generalizations (1967-1971):
   • Menon (1967): Generalization using single-variable polynomial f(x), defining ϕ_f(n)
   • Schemmel (1869): f(x) = x(x-1)···(x-b+1)
   • Nagell (1923), Cohen (1960): f(x) = x(b-x)
   • Stevens (1971): Multivariate generalization encompassing Jordan totient function
2. Modern Development (2022-2025):
   • Tóth (2022): Using e₁ and e_k, obtaining elegant product formulas
   • Csizmazia-Tóth (2025): General framework for multivariate polynomial systems, proving product forms
3. Restricted Linear Congruences (1913-2017):
   • Lehmer (1913), Rademacher (1925): Early work
   • Cohen (1955), Rearick (1963): Special cases
   • Bibak et al. (2017): General formulas for arbitrary parameters

Positioning of This Paper

1. Relative to Tóth (2022):
   • Extension: From {e₁,e_k} to {e₁,e₂}, {e₂,e_k} and more combinations
   • Deepening: Provides closed-form solutions for p=2 case
   • Unification: Establishes explicit connections to restricted linear congruences
2. Relative to Csizmazia-Tóth (2025):
   • Concretization: From general framework to explicit formulas for elementary symmetric polynomials
   • Computability: Provides computable expressions rather than existence results
   • Applicability: Connects to concrete number-theoretic problems
3. Relative to Bibak et al. (2017):
   • New Perspective: Unified treatment of restricted linear congruences through totient functions
   • New Tools: Utilizes quadratic form theory over finite fields
   • New Connections: Reveals equivalence with polynomial zero point counting

Advantages of This Paper

1. Theoretical Completeness: Establishes equivalence among three seemingly different problems
2. Computational Feasibility: Provides explicit, computable formulas
3. Methodological Innovation: Combines number theory, algebra, and combinatorial methods
4. Framework Unification: Recursive methods applicable to arbitrary elementary symmetric polynomials

Conclusions and Discussion

Main Conclusions

1. Theoretical Contributions:
   • Establishes inclusion-exclusion relationships between φ_F and ϕ_F
   • Derives explicit product forms for totient functions involving second elementary symmetric sum
   • Proves equivalence among generalized totient functions, finite field zero point counting, and restricted linear congruences
2. Concrete Results:
   • Provides complete formulas for N_k(e₂,p), N_k(e₁,e₂,p), N_k(e₂,e_k,p)
   • Furnishes computable expressions for k=3 and k=4 cases
   • Generalizes Menon's identity to new situations
3. Methodology:
   • Proposes recursive framework for arbitrary elementary symmetric polynomials
   • Develops generating function techniques for p=2 case
   • Establishes paradigm for unified treatment of multiple number-theoretic problems

Limitations

1. Computational Complexity:
   • Formulas become extremely complex for large k values (e.g., h_k(p) in Theorem 3.0.11)
   • General case ϕ_{1,2,k}(n) lacks explicit formula, only k=3 special case provided
2. Coverage Range:
   • Primarily focuses on e₂, with limited treatment of general e_j (2<j<k-1)
   • Non-elementary symmetric polynomials not addressed
3. Theoretical Depth:
   • Lacks deeper explanation of why these three problems are equivalent
   • Connections to other number-theoretic structures (modular forms, L-functions) unexplored
4. Practical Utility:
   • For large n, computing product forms still requires factorization
   • Quadratic character η computation remains complex in certain cases

Future Directions

1. Theoretical Extensions:
   • Research explicit formulas for general e_j (2<j<k-1)
   • Explore non-symmetric polynomial cases
   • Study finer structures for composite moduli
2. Computational Methods:
   • Develop efficient algorithms for computing N_k(J,p)
   • Research approximation methods for large parameter cases
   • Implement symbolic computation systems
3. Application Expansion:
   • Cryptographic applications (e.g., key distribution)
   • Coding theory applications
   • Connections to Ramanujan sums in signal processing
4. Deeper Connections:
   • Links to algebraic geometry (point counting on varieties)
   • Connections to analytic number theory (Dirichlet series)
   • Possible representation theory connections

In-Depth Evaluation

Strengths

1. Mathematical Rigor ⭐⭐⭐⭐⭐:
   • All theorems have complete proofs
   • Clear logic and rigorous argumentation
   • Meticulous treatment of special cases (p=2)
2. Innovation ⭐⭐⭐⭐:
   • First systematic treatment of second elementary symmetric sum totient function
   • Novel perspective establishing equivalence among three problems
   • Original generating function methods for p=2 case
3. Completeness ⭐⭐⭐⭐:
   • Covers both general theory and concrete examples
   • Includes both existence results and constructive algorithms
   • Contains multiple verification results (e.g., recovering Jordan function)
4. Readability ⭐⭐⭐⭐:
   • Clear structure progressing from simple to complex
   • Multiple concrete examples aid understanding
   • Figure 1 effectively summarizes main relationships
5. Theoretical Value ⭐⭐⭐⭐⭐:
   • Fills important gaps in Tóth's work
   • Provides unified framework for multiple number theory domains
   • Generalizes classical Menon's identity

Weaknesses

1. Computational Practicality ⭐⭐⭐:
   • Formulas become impractically complex for general k and complex J
   • Lacks algorithmic complexity analysis
   • No numerical examples or computational implementations
2. Breadth of Coverage ⭐⭐⭐:
   • Insufficient treatment of intermediate cases e_j (2<j<k-1)
   • Only k=3 case provided for ϕ_{1,2,...,k}
   • Some theorems (e.g., 3.0.11) have expressions too complex for practical use
3. Depth of Explanation ⭐⭐⭐:
   • Lacks deep mathematical intuition for why three problems are equivalent
   • Insufficient exploration of connections to other number-theoretic structures
   • Number-theoretic significance of certain formulas not fully clarified
4. Application Demonstration ⭐⭐:
   • While mentioning cryptography and coding theory connections, provides no concrete applications
   • Ramanujan sum connection only briefly mentioned in Remark
   • Lacks demonstration of solving actual problems

Impact Assessment

1. Theoretical Impact (Expected):
   • Short-term: Will become important reference in totient function generalization field
   • Mid-term: May inspire more research on symmetric polynomials and number theory
   • Long-term: Provides new paradigm for unified treatment of number-theoretic problems
2. Practical Value:
   • Cryptography: Restricted linear congruences have applications in key agreement
   • Coding Theory: Related to finite field structures
   • Algorithm Design: Provides theoretical foundation for certain counting problems
3. Reproducibility ⭐⭐⭐⭐:
   • Complete proofs enable verification
   • Concrete examples can be manually verified
   • Lacks code implementation, limiting large-scale verification
4. Potential for Follow-up Research ⭐⭐⭐⭐⭐:
   • Paves way for research on e_j (j>2)
   • Recursive framework can be further developed
   • Large space for interdisciplinary research

Applicable Scenarios

1. Theoretical Research:
   • Researchers studying totient function generalizations
   • Finite field theory researchers
   • Combinatorial number theory researchers
2. Practical Applications:
   • Cryptographic protocol design (computing solution counts for specific congruences)
   • Coding theory (related to finite field structures)
   • Pseudorandom number generation (utilizing number-theoretic properties)
3. Educational Use:
   • Demonstrating connections between number theory branches
   • Application examples of generating function techniques
   • Advanced applications of inclusion-exclusion principle

Comprehensive Rating

• Theoretical Contribution: 9/10
• Technical Innovation: 8/10
• Practical Value: 6/10
• Writing Quality: 8/10
• Overall Evaluation: 8/10

Summary: This is a high-quality number theory theory paper making substantial contributions to totient function generalization. The paper establishes profound connections among three seemingly different problems, provides complete characterization of the second elementary symmetric sum case, and develops systematic methodology. Main limitations are high computational complexity and insufficient practical application demonstration. For number theory theorists, this is an important reference; for applied researchers, further algorithmic optimization and concrete implementation are needed.

References (Key Citations in Paper)

1. Tóth, L. (2022). Another generalization of euler's arithmetic function and menon's identity. The Ramanujan Journal.
   Direct predecessor work of this paper
2. Csizmazia, N., & Tóth, L. (2025). Generalizations of euler's φ-function with respect to systems of polynomials of several variables.
   Provides general theoretical framework
3. Lidl, R., & Niederreiter, H. (1997). Finite fields. Cambridge University Press.
   Core reference for quadratic form theory
4. Bibak, K., et al. (2017). Restricted linear congruences. Journal of Number Theory, 171:128–144.
   Latest general results on restricted linear congruences
5. Menon, P. K. (1967). An extension of euler's function. Math Student, 35:55–59.
   Pioneering work on polynomial generalizations

Report Completion Date: Based on arXiv preprint of November 26, 2025
Report Nature: In-depth academic analysis
Target Audience: Number theory researchers, graduate students, scholars interested in totient function generalizations