Abdelaziz kaieb k deffirentiel

[benbechiraziz212-maker]

"""
Implementation of key results from:
"Parity of k-differentials in genus zero and one"
arXiv:2602.03722v1 [math.NT] 3 Feb 2026
Chen, Chen, Lau, Ono, Zhang

This module provides:

• Jacobi symbol computation
• N(n) counting function (Conjecture 1.1 / Theorem 1.2)
• Spin parity computation for genus 0 and 1 (Theorems 1.3-1.4)
• Numerical verification tools
  """

import math
from typing import List, Tuple, Optional
from functools import lru_cache

@lru_cache(maxsize=None)
def jacobi_symbol(a: int, k: int) -> int:
"""
Compute the Jacobi symbol (a/k) for odd k > 0.

Based on standard recursive algorithm using:
- Supplementary laws for (2/k) and (-1/k)
- Quadratic reciprocity

Args:
    a: Integer numerator
    k: Odd positive integer denominator

Returns:
    1, -1, or 0 (if gcd(a,k) > 1)

Examples:
    >>> jacobi_symbol(2, 7)
    1
    >>> jacobi_symbol(3, 11)
    -1
    >>> jacobi_symbol(4, 9)
    1
"""
if k <= 0 or k % 2 == 0:
    raise ValueError(f"k must be a positive odd integer, got {k}")

a = a % k
if a == 0:
    return 0
if a == 1:
    return 1

# Factor out powers of 2
e = 0
while a % 2 == 0:
    a //= 2
    e += 1

# Supplementary law for (2/k): (2/k) = (-1)^((k^2-1)/8)
if e % 2 == 0:
    s = 1
else:
    r = k % 8
    s = 1 if r in (1, 7) else -1

# Supplementary law for (-1/k): (-1/k) = (-1)^((k-1)/2)
if a % 4 == 3 and k % 4 == 3:
    s = -s

# Quadratic reciprocity
return s * jacobi_symbol(k % a, a)

def compute_N(n: int, k: int) -> int:
"""
Compute N(n) as defined in Conjecture 1.1:
Number of pairs (b1, b2) with:
- 1 ≤ b1, b2 ≤ (k-1)/2
- b1 + b2 > (k+1)/2 [equivalent to b1 + b2 ≥ (k+3)/2]
- b1 ≡ n·b2 (mod k)

Theorem 1.2 proves: N(n) ≡ ⌊(k+1)/4⌋ (mod 2) when gcd(n,k)=gcd(n+1,k)=1

Args:
    n: Integer parameter
    k: Odd integer ≥ 3

Returns:
    Count N(n)

Examples:
    >>> compute_N(1, 5)
    1
    >>> compute_N(2, 7)
    2
"""
if k < 3 or k % 2 == 0:
    raise ValueError(f"k must be an odd integer ≥ 3, got {k}")

m = (k - 1) // 2  # Upper bound for b1, b2
threshold = m + 1  # b1 + b2 > (k+1)/2 ⇔ b1 + b2 ≥ m+2? Let's verify:
# (k+1)/2 = (2m+1+1)/2 = (2m+2)/2 = m+1
# So condition is b1 + b2 > m+1 ⇔ b1 + b2 ≥ m+2
threshold = m + 2

count = 0
for b2 in range(1, m + 1):
    # Find b1 ≡ n·b2 (mod k) in range [1, k-1]
    b1_raw = (n * b2) % k
    if b1_raw == 0:
        b1_raw = k
    
    # We need b1 in [1, m] to count it
    if 1 <= b1_raw <= m:
        b1 = b1_raw
        if b1 + b2 >= threshold:
            count += 1

return count

def spin_parity_genus_zero(u: List[int], k: int) -> int:
"""
Compute spin parity for genus zero, odd k (Theorem 1.3).
Returns 0 for even parity, 1 for odd parity.

The parity is determined by n_k(u) (mod 2), where:
  n_k(u) = Σ_{q ∈ Q} #{i : v_q(m_i) ≢ v_q(k) (mod 2)}
and Q is the set of primes q | k with ⌊(q+1)/4⌋ odd.

Args:
    u: List of integers [m1, ..., mn] for differential type 2u = (2m1, ..., 2mn)
    k: Odd integer (k-differential)

Returns:
    0 (even parity) or 1 (odd parity)

Examples:
    >>> spin_parity_genus_zero([1, 1, 1], 3)
    0
    >>> spin_parity_genus_zero([2, 2], 5)
    1
"""
if k % 2 == 0:
    raise ValueError("k must be odd for parity type differentials")

# Get prime factorization of k
def prime_factorization(n: int) -> List[Tuple[int, int]]:
    factors = []
    d = 3
    while d * d <= n:
        if n % d == 0:
            cnt = 0
            while n % d == 0:
                n //= d
                cnt += 1
            factors.append((d, cnt))
        d += 2
    if n > 1:
        factors.append((n, 1))
    return factors

# Identify primes q where floor((q+1)/4) is odd
def is_odd_type_prime(q: int) -> bool:
    return ((q + 1) // 4) % 2 == 1

prime_factors = prime_factorization(k)
total = 0

for q, vq_k in prime_factors:
    if not is_odd_type_prime(q):
        continue
    
    # Count indices where v_q(m_i) has different parity than v_q(k)
    count_diff_parity = 0
    for m in u:
        # Compute v_q(|m|)
        vq_m = 0
        mm = abs(m)
        while mm % q == 0 and mm > 0:
            vq_m += 1
            mm //= q
        
        if (vq_m % 2) != (vq_k % 2):
            count_diff_parity += 1
    
    total += count_diff_parity

return total % 2

def spin_parity_genus_one(u: List[int], k: int, d: int) -> int:
"""
Compute spin parity for genus one, odd k, rotation number d (Theorem 1.4).
Returns 0 for even parity, 1 for odd parity.

Parity = n_k(2u) + d + 1 (mod 2)

Args:
    u: List of integers for differential type 2u
    k: Odd integer (k-differential)
    d: Rotation number (positive integer divisor of gcd of entries in 2u)

Returns:
    0 (even parity) or 1 (odd parity)
"""
n_val = spin_parity_genus_zero(u, k)  # n_k(2u) uses same formula as genus zero
return (n_val + d + 1) % 2

def verify_theorem_1_2(k_max: int = 101, verbose: bool = False) -> Tuple[bool, List[Tuple[int, int, int, int]]]:
"""
Numerically verify Theorem 1.2 (formerly Conjecture 1.1) for odd k up to k_max.

Theorem: For odd k and gcd(n,k)=gcd(n+1,k)=1,
         N(n) ≡ ⌊(k+1)/4⌋ (mod 2)

Args:
    k_max: Maximum k to test
    verbose: Print detailed output

Returns:
    (all_passed, failures) where failures is list of (k, n, N_val, expected_parity)
"""
failures = []
total_tests = 0

if verbose:
    print(f"Verifying Theorem 1.2 for odd 3 ≤ k ≤ {k_max}...")

for k in range(3, k_max + 1, 2):
    expected_parity = ((k + 1) // 4) % 2
    
    for n in range(1, k):
        if math.gcd(n, k) != 1 or math.gcd(n + 1, k) != 1:
            continue
        
        total_tests += 1
        N_val = compute_N(n, k)
        actual_parity = N_val % 2
        
        if actual_parity != expected_parity:
            failures.append((k, n, N_val, expected_parity))
            if verbose:
                print(f"❌ FAIL: k={k}, n={n}, N(n)={N_val} (parity {actual_parity}), expected {expected_parity}")

all_passed = len(failures) == 0
if verbose:
    if all_passed:
        print(f"✅ All {total_tests} tests passed for odd 3 ≤ k ≤ {k_max}")
    else:
        print(f"❌ {len(failures)} failures out of {total_tests} tests")

return all_passed, failures

if name == "main":
# Quick self-test
print("="*70)
print("Parity of k-Differentials: Python Implementation")
print("arXiv:2602.03722v1 [math.NT] 3 Feb 2026")
print("="*70)

# Verify Theorem 1.2
print("\n[1/3] Verifying Theorem 1.2 (Conjecture 1.1)...")
passed, _ = verify_theorem_1_2(51, verbose=False)
print(f"   Result: {'✅ PASSED' if passed else '❌ FAILED'} for k ≤ 51")

# Example N(n) computations
print("\n[2/3] Example N(n) computations:")
examples = [(1, 5), (2, 7), (3, 9), (4, 11), (5, 13)]
for n, k in examples:
    if math.gcd(n, k) == 1 and math.gcd(n+1, k) == 1:
        N_val = compute_N(n, k)
        expected = ((k + 1) // 4) % 2
        status = "✓" if (N_val % 2) == expected else "✗"
        print(f"   N({n:2d}) for k={k:2d}: {N_val:3d} (parity {N_val%2}) → expected {expected} {status}")

# Spin parity examples
print("\n[3/3] Spin parity examples (genus zero):")
test_cases = [
    ([1, 1, 1], 3),
    ([2, 2], 5),
    ([1, 3], 7),
    ([2, 4, 6], 9),
]
for u, k in test_cases:
    parity = spin_parity_genus_zero(u, k)
    print(f"   u={str(u):15s}, k={k:2d} → parity = {'odd' if parity else 'even'}")

print("\n" + "="*70)
print("For detailed examples, run: python examples.py")
print("For tests, run: pytest tests/")
print("="*70)