main.sagetex.sage

## -*- encoding: utf-8 -*-
## This file (main.sagetex.sage) was *autogenerated* from main.tex with sagetex.sty version 2021/10/16 v3.6.
import sagetex
_st_ = sagetex.SageTeXProcessor('main', version='2021/10/16 v3.6', version_check=True)
_st_.current_tex_line = 226
_st_.blockbegin()
try:
   # Compute cyclotomic polynomials for n = 1 to 20
   cyclotomic_data = {}
   for n in range(1, 21):
   phi_n = cyclotomic_polynomial(n)
   degree = phi_n.degree()
   coeffs = phi_n.coefficients(sparse=False)
 
   cyclotomic_data[n] = {
   'polynomial': phi_n,
   'degree': degree,
   'coefficients': coeffs,
   'euler_phi': euler_phi(n)
   }
 
   # Display cyclotomic polynomials for small n
   print("Cyclotomic Polynomials Φ_n(x) for n = 1 to 12:")
   for n in range(1, 13):
   phi_n = cyclotomic_data[n]['polynomial']
   degree = cyclotomic_data[n]['degree']
   print(f"Φ_{n}(x) = {phi_n}, degree = {degree}")
 
   # Verify that degree equals Euler's totient function
   print("\nVerification: deg(Φ_n) = φ(n)")
   for n in range(1, 13):
   degree = cyclotomic_data[n]['degree']
   euler_val = cyclotomic_data[n]['euler_phi']
   print(f"n = {n}: deg(Φ_{n}) = {degree}, φ({n}) = {euler_val}, Equal: {degree == euler_val}")
except:
 _st_.goboom(254)
_st_.blockend()
_st_.current_tex_line = 277
_st_.blockbegin()
try:
   # Verify the fundamental identity for several values of n
   print(r"Verification of $x^n - 1 = \prod_{d \mid n} \Phi_d(x)$:")
 
   for n in [6, 8, 12, 15]:
   # Left side: x^n - 1
   left_side = x^n - 1
 
   # Right side: product of \Phi_d(x) for all d dividing n
   divisors = [d for d in range(1, n+1) if n % d == 0]
   right_side = 1
   for d in divisors:
   right_side *= cyclotomic_polynomial(d)
 
   # Verify equality (no need to expand - SageMath polynomials are already expanded)
   equality = (left_side == right_side)
 
   print(f"n = {n}: divisors = {divisors}")
   print(f"  x^{n} - 1 = {left_side}")
   print(f"  Product = {right_side}")
   print(f"  Equal: {equality}")
 
   # Analyze coefficient patterns in cyclotomic polynomials
   print("\nCoefficient analysis:")
   for n in [105, 210, 420]:  # Cases where coefficients exceed ±1
   if n <= 20:  # Only for computed cases
   continue
   phi_n = cyclotomic_polynomial(n)
   coeffs = phi_n.coefficients(sparse=False)
   max_coeff = max(abs(c) for c in coeffs)
   print(f"\\Phi_{n}(x): max |coefficient| = {max_coeff}")
except:
 _st_.goboom(308)
_st_.blockend()
_st_.current_tex_line = 314
_st_.blockbegin()
try:
   # Analysis of roots structure for visualization
   print("Roots of Unity Analysis:")
   for n in [6, 8, 12, 16]:
   all_roots = n
   primitive_roots = euler_phi(n)
   print(f"n = {n}: Total {n}-th roots of unity: {all_roots}")
   print(f"       Primitive {n}-th roots of unity: {primitive_roots}")
   print(f"       Cyclotomic polynomial Φ_{n}(x) has degree {primitive_roots}")
except:
 _st_.goboom(323)
_st_.blockend()
_st_.current_tex_line = 348
_st_.blockbegin()
try:
   # Analyze Galois groups for cyclotomic fields
   print("Galois Groups of Cyclotomic Fields Q(ζ_n)/Q:")
 
   galois_data = {}
   for n in range(1, 17):
   # Units group (Z/nZ)*
   units_group = Integers(n).unit_group()
   group_order = units_group.order()
   group_structure = units_group.invariants()
 
   # Field degree [Q(ζ_n) : Q] = φ(n)
   field_degree = euler_phi(n)
 
   galois_data[n] = {
   'field_degree': field_degree,
   'group_order': group_order,
   'group_structure': group_structure,
   'units_group': units_group
   }
 
   print(f"n = {n:2d}: [Q(ζ_{n}) : Q] = {field_degree:2d}, "
   f"|Gal| = {group_order:2d}, structure = {group_structure}")
 
   # Detailed analysis for specific cases
   print("\nDetailed Galois group analysis:")
 
   interesting_cases = [8, 12, 15, 16, 20]
   for n in interesting_cases:
   if n >= len(galois_data):
   continue
 
   units = Integers(n).unit_group()
   elements = [a for a in range(1, n) if gcd(a, n) == 1]
 
   print(f"\nn = {n}: Q(ζ_{n})/Q")
   print(f"  Units (Z/{n}Z)* = {{{', '.join(map(str, elements))}}}")
   print(f"  Group structure: {units.invariants()}")
   print(f"  Cyclic: {units.is_cyclic()}")
 
   # Generator information for cyclic groups
   if units.is_cyclic():
   # Find a generator
   for a in elements:
   order = Integers(n)(a).multiplicative_order()
   if order == len(elements):
   print(f"  Generator: {a} (order {order})")
   break
except:
 _st_.goboom(396)
_st_.blockend()
_st_.current_tex_line = 408
_st_.blockbegin()
try:
   # Analyze ramification patterns
   print("Ramification Analysis in Cyclotomic Fields:")
 
   def analyze_ramification(n):
   """Analyze ramification of primes in Q(ζ_n)"""
   print(f"\nQ(ζ_{n})/Q ramification:")
 
   # Get prime divisors of n
   n_factorization = factor(n)
   ramified_primes = [p for p, e in n_factorization]
 
   print(f"  n = {n} = {n_factorization}")
   print(f"  Ramified primes: {ramified_primes}")
 
   # Analyze each small prime
   for p in [2, 3, 5, 7, 11]:
   if p > n:
   break
 
   if p not in ramified_primes:
   # Unramified case - compute splitting behavior
   if gcd(p, n) == 1:
   f = Integers(n)(p).multiplicative_order()
   else:
   f = "undefined"
   print(f"  p = {p}: unramified, inertia degree f = {f}")
   else:
   # Ramified case - find the exponent of p in the factorization
   ramification_index = 0
   for prime, exp in n_factorization:
   if prime == p:
   ramification_index = exp
   break
   totally_ramified = ramification_index == 1
   print(f"  p = {p}: ramified (e = {ramification_index}), "
   f"totally ramified: {totally_ramified}")
 
   # Analyze several cyclotomic fields
   for n in [8, 12, 15, 20, 24]:
   analyze_ramification(n)
except:
 _st_.goboom(449)
_st_.blockend()
_st_.current_tex_line = 468
_st_.blockbegin()
try:
   import os
   if not os.path.exists('figures'):
   os.makedirs('figures')
 
   # Demonstrate quadratic reciprocity computations
   print("Quadratic Reciprocity Examples:")
 
   def legendre_symbol(a, p):
   """Compute Legendre symbol (a/p)"""
   return kronecker_symbol(a, p)
 
   def verify_reciprocity(p, q):
   """Verify quadratic reciprocity for primes p, q"""
   left_side = legendre_symbol(p, q) * legendre_symbol(q, p)
   right_side = (-1)**((p-1)//2 * (q-1)//2)
   return left_side == right_side
 
   # Test quadratic reciprocity for several prime pairs
   prime_pairs = [(3, 5), (3, 7), (5, 7), (7, 11), (11, 13), (13, 17)]
 
   for p, q in prime_pairs:
   leg_p_q = legendre_symbol(p, q)
   leg_q_p = legendre_symbol(q, p)
   product = leg_p_q * leg_q_p
   expected = (-1)**((p-1)//2 * (q-1)//2)
   verified = verify_reciprocity(p, q)
 
   print(f"p = {p}, q = {q}: ({p}/{q}) = {leg_p_q:2d}, ({q}/{p}) = {leg_q_p:2d}")
   print(f"  Product = {product:2d}, Expected = {expected:2d}, Verified: {verified}")
 
   # Analysis summary for the visualization
   print("\nQuadratic reciprocity visualization generated showing Legendre symbols.")
   print("The reciprocity pattern demonstrates the fundamental law:")
   print("For distinct odd primes p, q: (p/q)(q/p) = (-1)^((p-1)/2 * (q-1)/2)")
 
   # Additional analysis of specific cases
   print("\nDetailed reciprocity analysis:")
   small_primes = [3, 5, 7, 11, 13]
   for i, p in enumerate(small_primes):
   for j, q in enumerate(small_primes):
   if i < j:  # Only examine pairs once
   symbol_pq = legendre_symbol(p, q)
   symbol_qp = legendre_symbol(q, p)
   print(f"({p}/{q}) = {symbol_pq:2d}, ({q}/{p}) = {symbol_qp:2d}, Product = {symbol_pq * symbol_qp:2d}")
except:
 _st_.goboom(513)
_st_.blockend()
_st_.current_tex_line = 524
_st_.blockbegin()
try:
   # Investigate cyclotomic class numbers
   print("Class Numbers of Cyclotomic Fields:")
 
   def compute_cyclotomic_info(n):
   """Compute information about the n-th cyclotomic field"""
   # For computational feasibility, we focus on small n
   if n > 20:
   return None
 
   field_degree = euler_phi(n)
   discriminant_factor_count = len([p for p, e in factor(n)])
 
   return {
       'n': n,
       'degree': field_degree,
       'conductor': n,
       'discriminant_complexity': discriminant_factor_count
     }
 
   # Analyze cyclotomic fields
   cyclotomic_info = []
   for n in range(1, 21):
   info = compute_cyclotomic_info(n)
   if info:
   cyclotomic_info.append(info)
 
   print("Cyclotomic Field Data:")
   print("n     degree  conductor  discriminant_complexity")
   print("-" * 45)
   for info in cyclotomic_info:
   print(f"{info['n']:2d}    {info['degree']:3d}     {info['conductor']:3d}        {info['discriminant_complexity']:3d}")
 
   # Focus on specific interesting cases
   interesting_fields = [7, 8, 9, 12, 15, 16, 20]
   print(f"\nDetailed analysis for selected cyclotomic fields:")
 
   for n in interesting_fields:
   if n <= 20:
   phi_n = euler_phi(n)
   units_structure = Integers(n).unit_group().invariants()
   print(f"Q(ζ_{n}): degree {phi_n}, Gal ≅ {units_structure}")
except:
 _st_.goboom(566)
_st_.blockend()
_st_.current_tex_line = 576
_st_.blockbegin()
try:
   # Analyze computational complexity of cyclotomic polynomial operations
   print("Computational Complexity Analysis:")
 
   def time_cyclotomic_computation(n_max):
   """Analyze timing for cyclotomic polynomial computations"""
   import time
 
   timing_data = []
 
   for n in range(1, min(n_max + 1, 101)):  # Limit for computational feasibility
   start_time = time.time()
 
   # Compute cyclotomic polynomial
   phi_n = cyclotomic_polynomial(n)
   degree = phi_n.degree()
   height = max(abs(c) for c in phi_n.coefficients(sparse=False))
 
   end_time = time.time()
   computation_time = end_time - start_time
 
   timing_data.append({
       'n': int(n),
       'degree': int(degree),
       'height': int(height),
       'time': float(computation_time)
     })
 
   if n <= 30 or n % 10 == 0:
   print(f"n = {n:3d}: degree = {degree:3d}, "
   f"height = {height:4d}, time = {computation_time:.4f}s")
 
   return timing_data
 
   # Perform timing analysis for moderate values
   print("Timing analysis for cyclotomic polynomial computation:")
   timing_results = time_cyclotomic_computation(50)
 
   # Summary analysis of complexity results
   print("\nComplexity Analysis Summary:")
   print(f"Analyzed cyclotomic polynomials for n = 1 to {len(timing_results)}")
 
   n_values = [data['n'] for data in timing_results]
   degrees = [data['degree'] for data in timing_results]
   heights = [data['height'] for data in timing_results]
   times = [data['time'] for data in timing_results]
 
   print(f"Maximum degree observed: {max(degrees)} (for n = {n_values[degrees.index(max(degrees))]})")
   print(f"Maximum coefficient height: {max(heights)} (for n = {n_values[heights.index(max(heights))]})")
   print(f"Total computation time: {sum(times):.4f} seconds")
 
   # Highlight some interesting cases
   interesting_n = [12, 15, 20, 24, 30, 40]
   print("\nComplexity for selected values:")
   for n in interesting_n:
   if n <= len(timing_results):
   idx = n - 1
   print(f"n = {n:2d}: degree = {degrees[idx]:2d}, height = {heights[idx]:3d}, time = {times[idx]:.4f}s")
except:
 _st_.goboom(634)
_st_.blockend()
_st_.endofdoc()