character_exploration.py

#!/usr/bin/env python3
"""
character_exploration.py

Comprehensive exploration of Dirichlet characters and their properties.
Demonstrates character enumeration, evaluation, arithmetic, and analysis.

Author: libadic team
"""

import sys
from collections import defaultdict
from typing import List, Dict

# Add libadic to path
sys.path.insert(0, '/mnt/c/Users/asmit/github/libadic/build')

try:
    import libadic
except ImportError:
    print("Error: libadic module not found. Please build the library first.")
    sys.exit(1)


def print_header(title: str, char: str = "="):
    """Print a formatted header."""
    print(f"\n{char * 60}")
    print(title)
    print(char * 60)


def explore_character_structure(n: int, p: int):
    """
    Explore the structure of Dirichlet characters mod n.
    """
    print_header(f"CHARACTER STRUCTURE MOD {n}")
    
    # Enumerate all characters
    all_chars = libadic.enumerate_characters(n, p)
    print(f"\nTotal characters mod {n}: {len(all_chars)}")
    
    # Get primitive characters
    primitive = libadic.enumerate_primitive_characters(n, p)
    print(f"Primitive characters: {len(primitive)}")
    print(f"Imprimitive characters: {len(all_chars) - len(primitive)}")
    
    # Group by conductor
    by_conductor = defaultdict(list)
    for chi in all_chars:
        by_conductor[chi.get_conductor()].append(chi)
    
    print(f"\nCharacters by conductor:")
    for cond in sorted(by_conductor.keys()):
        count = len(by_conductor[cond])
        print(f"  Conductor {cond}: {count} characters")
    
    # Group by order
    by_order = defaultdict(list)
    for chi in all_chars:
        by_order[chi.get_order()].append(chi)
    
    print(f"\nCharacters by order:")
    for order in sorted(by_order.keys()):
        count = len(by_order[order])
        print(f"  Order {order}: {count} characters")
        # Note: Should have φ(order) characters of each order
    
    # Parity classification
    odd_count = sum(1 for chi in all_chars if chi.is_odd())
    even_count = sum(1 for chi in all_chars if chi.is_even())
    
    print(f"\nParity classification:")
    print(f"  Odd characters (χ(-1) = -1): {odd_count}")
    print(f"  Even characters (χ(-1) = 1): {even_count}")
    
    return all_chars, primitive


def display_character_table(chars: List, n: int, max_chars: int = 5):
    """
    Display character table showing values.
    """
    print_header("CHARACTER TABLE")
    
    # Limit number of characters to display
    display_chars = chars[:max_chars]
    
    print(f"\nShowing first {len(display_chars)} characters mod {n}:")
    print("\n  n |", end="")
    for i in range(len(display_chars)):
        print(f" χ_{i:2d}", end="")
    print("\n" + "-" * (5 + 5 * len(display_chars)))
    
    # Show values for small n
    for a in range(1, min(n, 15)):
        if libadic.gcd(libadic.BigInt(a), libadic.BigInt(n)) == libadic.BigInt(1):
            print(f" {a:2d} |", end="")
            for chi in display_chars:
                val = chi.evaluate_at(a)
                print(f" {val:3d}", end="")
            print()
    
    if n > 15:
        print(" ...")


def verify_character_properties(chi, n: int, p: int):
    """
    Verify mathematical properties of a character.
    """
    print_header("CHARACTER PROPERTIES VERIFICATION")
    
    print(f"\nCharacter mod {n}:")
    print(f"  Modulus: {chi.get_modulus()}")
    print(f"  Conductor: {chi.get_conductor()}")
    print(f"  Order: {chi.get_order()}")
    print(f"  Is primitive: {chi.is_primitive()}")
    print(f"  Is principal: {chi.is_principal()}")
    print(f"  Parity: {'odd' if chi.is_odd() else 'even'}")
    
    # Property 1: Completely multiplicative
    print("\n1. Multiplicativity Test:")
    success = True
    for a in [2, 3, 5]:
        for b in [3, 4, 7]:
            if a >= n or b >= n:
                continue
            ab = (a * b) % n
            
            # Skip if not coprime
            if (libadic.gcd(libadic.BigInt(a), libadic.BigInt(n)) != libadic.BigInt(1) or
                libadic.gcd(libadic.BigInt(b), libadic.BigInt(n)) != libadic.BigInt(1) or
                libadic.gcd(libadic.BigInt(ab), libadic.BigInt(n)) != libadic.BigInt(1)):
                continue
            
            chi_a = chi.evaluate_at(a)
            chi_b = chi.evaluate_at(b)
            chi_ab = chi.evaluate_at(ab)
            
            if chi_ab == chi_a * chi_b:
                print(f"  ✓ χ({a}×{b}) = χ({a})×χ({b}) = {chi_ab}")
            else:
                print(f"  ✗ χ({a}×{b}) ≠ χ({a})×χ({b})")
                success = False
    
    if success:
        print("  Result: ✓ Character is multiplicative")
    
    # Property 2: Periodicity
    print("\n2. Periodicity Test:")
    test_vals = [3, 5, 7]
    for a in test_vals:
        if a >= n:
            continue
        chi_a = chi.evaluate_at(a)
        chi_a_plus_n = chi.evaluate_at(a + n)
        
        if chi_a == chi_a_plus_n:
            print(f"  ✓ χ({a}) = χ({a + n}) = {chi_a}")
        else:
            print(f"  ✗ χ({a}) ≠ χ({a + n})")
    
    # Property 3: Order divides φ(n)
    print("\n3. Order Property:")
    order = chi.get_order()
    
    # Compute φ(n) - simplified for prime case
    if n == p and all(n % i != 0 for i in range(2, int(n**0.5) + 1)):
        phi_n = n - 1
    else:
        # General Euler's totient would be needed
        phi_n = n  # Placeholder
    
    if phi_n % order == 0:
        print(f"  ✓ Order {order} divides φ({n})")
    else:
        print(f"  ✗ Order {order} does not divide φ({n})")
    
    # Property 4: Character to its order is principal
    print("\n4. Order Test:")
    chi_power = chi ** order
    is_principal = all(
        chi_power.evaluate_at(a) == 1
        for a in range(1, min(n, 20))
        if libadic.gcd(libadic.BigInt(a), libadic.BigInt(n)) == libadic.BigInt(1)
    )
    
    if is_principal:
        print(f"  ✓ χ^{order} is the principal character")
    else:
        print(f"  ✗ χ^{order} is not principal")


def demonstrate_character_arithmetic(chars: List, n: int, p: int):
    """
    Demonstrate character group operations.
    """
    print_header("CHARACTER ARITHMETIC")
    
    if len(chars) < 2:
        print("Need at least 2 characters for arithmetic demonstration")
        return
    
    chi1 = chars[0]
    chi2 = chars[1] if len(chars) > 1 else chars[0]
    
    print(f"\nCharacter 1: order={chi1.get_order()}, {'odd' if chi1.is_odd() else 'even'}")
    print(f"Character 2: order={chi2.get_order()}, {'odd' if chi2.is_odd() else 'even'}")
    
    # Multiplication
    print("\n1. Character Multiplication:")
    chi_prod = chi1 * chi2
    print(f"  χ₁ × χ₂: order={chi_prod.get_order()}")
    
    # Verify pointwise multiplication
    for a in [2, 3, 5, 7]:
        if a >= n:
            continue
        if libadic.gcd(libadic.BigInt(a), libadic.BigInt(n)) != libadic.BigInt(1):
            continue
            
        v1 = chi1.evaluate_at(a)
        v2 = chi2.evaluate_at(a)
        vp = chi_prod.evaluate_at(a)
        
        print(f"  χ₁({a})={v1}, χ₂({a})={v2}, (χ₁×χ₂)({a})={vp}")
        assert vp == v1 * v2
    
    # Powers
    print("\n2. Character Powers:")
    for k in [2, 3]:
        chi_power = chi1 ** k
        print(f"  χ₁^{k}: order={chi_power.get_order()}")
        
        # Verify
        a = 3 if 3 < n else 2
        if libadic.gcd(libadic.BigInt(a), libadic.BigInt(n)) == libadic.BigInt(1):
            v = chi1.evaluate_at(a)
            vk = chi_power.evaluate_at(a)
            print(f"    χ₁({a})^{k} = {v}^{k} = {v**k} ≟ {vk}")
    
    # Inverse
    print("\n3. Character Inverse:")
    order1 = chi1.get_order()
    chi_inv = chi1 ** (order1 - 1)  # χ^(-1) = χ^(order-1)
    
    # Verify χ × χ^(-1) = principal
    chi_identity = chi1 * chi_inv
    
    is_principal = True
    for a in range(1, min(n, 10)):
        if libadic.gcd(libadic.BigInt(a), libadic.BigInt(n)) != libadic.BigInt(1):
            continue
        if chi_identity.evaluate_at(a) != 1:
            is_principal = False
            break
    
    if is_principal:
        print(f"  ✓ χ × χ^{order1-1} is principal (identity)")
    else:
        print(f"  ✗ Inverse test failed")


def analyze_character_values(chi, n: int, p: int, precision: int):
    """
    Analyze character values and their p-adic lifts.
    """
    print_header("CHARACTER VALUES ANALYSIS")
    
    print(f"\nCharacter mod {n}, lifted to p={p}-adic:")
    
    # Integer values vs p-adic lifts
    print("\n  n | χ(n) | p-adic lift")
    print("-" * 35)
    
    for a in range(1, min(n, 15)):
        if libadic.gcd(libadic.BigInt(a), libadic.BigInt(n)) != libadic.BigInt(1):
            val_int = 0
            val_str = "  0"
        else:
            val_int = chi.evaluate_at(a)
            val_zp = chi.evaluate(a, precision)
            val_str = f"{val_zp.value:3d}"
        
        print(f" {a:2d} | {val_int:4d} | {val_str}")
    
    # Analyze value distribution
    value_counts = defaultdict(int)
    for a in range(1, n):
        if libadic.gcd(libadic.BigInt(a), libadic.BigInt(n)) == libadic.BigInt(1):
            val = chi.evaluate_at(a)
            value_counts[val] += 1
    
    print(f"\nValue distribution:")
    for val in sorted(value_counts.keys()):
        count = value_counts[val]
        print(f"  Value {val:3d}: appears {count} times")
    
    # For primitive characters, show Teichmüller lifts
    if chi.is_primitive():
        print(f"\nTeichmüller lifts (first few):")
        for a in [2, 3, 5]:
            if a >= n:
                continue
            if libadic.gcd(libadic.BigInt(a), libadic.BigInt(n)) != libadic.BigInt(1):
                continue
            
            val_int = chi.evaluate_at(a)
            if val_int != 0:
                # The evaluate method uses Teichmüller lift
                val_zp = chi.evaluate(a, precision)
                print(f"  ω(χ({a})) = {val_zp.value} in Z_{p}")


def explore_principal_character(chars: List, n: int):
    """
    Find and analyze the principal character.
    """
    print_header("PRINCIPAL CHARACTER")
    
    # Find principal character
    principal = None
    for chi in chars:
        if chi.is_principal():
            principal = chi
            break
    
    if not principal:
        # Check manually
        for chi in chars:
            is_principal = all(
                chi.evaluate_at(a) == 1
                for a in range(1, min(n, 20))
                if libadic.gcd(libadic.BigInt(a), libadic.BigInt(n)) == libadic.BigInt(1)
            )
            if is_principal:
                principal = chi
                break
    
    if principal:
        print(f"\nFound principal character mod {n}")
        print(f"  Order: {principal.get_order()} (should be 1)")
        print(f"  Conductor: {principal.get_conductor()}")
        
        # Verify it's identity
        print("\n  Verification (first few values):")
        for a in range(1, min(n, 10)):
            if libadic.gcd(libadic.BigInt(a), libadic.BigInt(n)) == libadic.BigInt(1):
                val = principal.evaluate_at(a)
                print(f"    χ₀({a}) = {val}")
    else:
        print(f"\nNo principal character found (unexpected!)")


def character_orthogonality_test(chars: List, n: int):
    """
    Test orthogonality relations for characters.
    """
    print_header("CHARACTER ORTHOGONALITY")
    
    if len(chars) < 2:
        print("Need at least 2 characters for orthogonality test")
        return
    
    print(f"\nTesting: Σ_a χ₁(a)χ₂(a)* = 0 for χ₁ ≠ χ₂")
    
    # Test first few pairs
    max_pairs = min(3, len(chars) * (len(chars) - 1) // 2)
    pair_count = 0
    
    for i in range(len(chars)):
        for j in range(i + 1, len(chars)):
            if pair_count >= max_pairs:
                break
            
            chi1 = chars[i]
            chi2 = chars[j]
            
            # Compute inner product
            inner_prod = 0
            for a in range(1, n):
                if libadic.gcd(libadic.BigInt(a), libadic.BigInt(n)) == libadic.BigInt(1):
                    # χ₂(a)* = χ₂(a)^(-1) for our integer-valued characters
                    val1 = chi1.evaluate_at(a)
                    val2 = chi2.evaluate_at(a)
                    inner_prod += val1 * val2  # Should use complex conjugate in general
            
            print(f"  χ_{i} · χ_{j}: sum = {inner_prod}")
            
            if inner_prod == 0:
                print(f"    ✓ Orthogonal")
            else:
                # Might be off by a constant factor
                print(f"    Note: Non-zero (may need conjugation)")
            
            pair_count += 1
            
        if pair_count >= max_pairs:
            break
    
    print(f"\nTested {pair_count} character pairs")


def main():
    """Main exploration routine."""
    
    print_header("DIRICHLET CHARACTER EXPLORATION", "=")
    
    # Configuration
    test_moduli = [5, 7, 11]
    p = 5  # Prime for p-adic computations
    precision = 20
    
    for n in test_moduli:
        print(f"\n{'='*60}")
        print(f"EXPLORING CHARACTERS MOD {n}")
        print('='*60)
        
        # Basic structure
        all_chars, primitive = explore_character_structure(n, p)
        
        # Character table
        display_character_table(primitive, n)
        
        # Pick a non-trivial character for detailed analysis
        if len(primitive) > 1:
            # Get first non-principal character
            chi = None
            for c in primitive:
                if not c.is_principal():
                    chi = c
                    break
            
            if chi:
                # Detailed properties
                verify_character_properties(chi, n, p)
                
                # Value analysis
                analyze_character_values(chi, n, p, precision)
        
        # Character arithmetic
        if len(primitive) >= 2:
            demonstrate_character_arithmetic(primitive, n, p)
        
        # Principal character
        explore_principal_character(all_chars, n)
        
        # Orthogonality (brief test)
        if len(primitive) >= 2:
            character_orthogonality_test(primitive[:4], n)
    
    print("\n" + "="*60)
    print("CHARACTER EXPLORATION COMPLETE")
    print("="*60)
    
    print("\nKey Findings:")
    print("  • Character enumeration working correctly")
    print("  • Multiplicative property verified")
    print("  • Character arithmetic (multiplication, powers) functional")
    print("  • Principal character identified")
    print("  • Values can be lifted to p-adic numbers")
    
    return 0


if __name__ == "__main__":
    sys.exit(main())