腾讯Hyra开源模型攻克50年数学难题深度解析：加法组合学与十二进制结构的科研智能体新范式

"""
Hyra Core Construction: Base-12 Digit Structure with CRT
实现和差集构造的核心算法
"""

import math
from typing import List, Set, Tuple
from itertools import product
import numpy as np


def chinese_remainder_theorem(remainders: List[int], moduli: List[int]) -> int:
    """
    中国剩余定理实现
    给定同余式组 x ≡ remainders[i] (mod moduli[i])，求解 x
    """
    M = 1
    for m in moduli:
        M *= m
    
    result = 0
    for a_i, m_i in zip(remainders, moduli):
        M_i = M // m_i
        # 计算 M_i 在模 m_i 下的逆元
        inv = pow(M_i, -1, m_i)
        result = (result + a_i * M_i * inv) % M
    
    return result


def construct_base12_digit_set(K: int, digit_subset: List[int]) -> List[int]:
    """
    构造十二进制数字部件
    
    参数:
        K: 每个数字的表示长度
        digit_subset: 允许使用的十二进制数字子集
    
    返回:
        构造的整数集合（列表形式）
    """
    if not digit_subset:
        digit_subset = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
    
    # 生成所有可能的数字序列
    # 每个位置从 digit_subset 中选择一个数字
    # 注意：这里为了演示，使用简化的构造
    
    base = 12
    result = []
    
    # 实际构造中，数字序列有特定的约束条件
    # 此处简化展示核心思想
    for digits in product(digit_subset, repeat=K):
        value = 0
        for i, d in enumerate(digits):
            value += d * (base ** i)
        result.append(value)
    
    return result


def compute_sumset(A: Set[int]) -> Set[int]:
    """计算和集 A+A"""
    result = set()
    for a in A:
        for b in A:
            result.add(a + b)
    return result


def compute_diffset(A: Set[int]) -> Set[int]:
    """计算差集 A-A"""
    result = set()
    for a in A:
        for b in A:
            result.add(a - b)
    return result


def compute_exponent(A: Set[int]) -> float:
    """
    计算 C(A) = log σ(A) / log δ(A)
    其中 σ(A) = |A+A|/|A|, δ(A) = |A-A|/|A|
    """
    n = len(A)
    sumset = compute_sumset(A)
    diffset = compute_diffset(A)
    
    sigma = len(sumset) / n
    delta = len(diffset) / n
    
    if sigma <= 1 or delta <= 1:
        return 0.0
    
    return math.log(sigma) / math.log(delta)


def construct_crt_additive_basis(moduli: List[int], basis_size: int) -> Tuple[List[int], List[int]]:
    """
    使用CRT构造对称加法基
    
    参数:
        moduli: 互质的模数列表
        basis_size: 每个循环群上的基大小
    
    返回:
        (crt_elements, group_sizes)
    """
    # 在每个循环群 Z_{m_i} 上构造对称加法基
    group_bases = []
    for m in moduli:
        # 选取对称基: ±1, ±2, ..., ±basis_size
        base = []
        for i in range(1, basis_size + 1):
            base.append(i % m)
            base.append((-i) % m)
        group_bases.append(base)
    
    # 通过CRT组合
    crt_elements = []
    for combo in product(*group_bases):
        element = chinese_remainder_theorem(list(combo), moduli)
        crt_elements.append(element)
    
    return crt_elements, moduli


def construct_hyra_family(K: int, epsilon: float) -> List[int]:
    """
    构造Hyra论文中的集合族 A_K
    
    参数:
        K: 规模参数（越大越接近2）
        epsilon: 目标精度
    
    返回:
        构造的集合 A_K
    """
    # 十二进制数字部件
    base = 12
    # 选择数字子集: 控制差集大小的关键
    # 使用特定模式的数字使得差集较小
    digit_subset = [0, 1, 4, 5, 8, 9]  # 精心选择的子集
    
    core = construct_base12_digit_set(K, digit_subset)
    
    # CRT 模数选择
    # 使用互质模数以最大化组合效果
    moduli = [2 * K + 1, 3 * K + 1, 5 * K + 1]
    # 确保模数互质
    moduli = [m for m in moduli if all(
        math.gcd(m, m2) == 1 for m2 in moduli if m2 != m
    )]
    
    # 构造加法基
    basis_size = int(math.log(K) * 2)
    crt_elements, _ = construct_crt_additive_basis(moduli, basis_size)
    
    # 组合核心构造与CRT基
    # 实际论文中使用更复杂的组合方式
    result = []
    scale = 12 ** (K + 1)
    for c in core:
        for b in crt_elements[:min(len(crt_elements), K)]:
            result.append(c + scale * b)
    
    return result


def demonstrate_convergence(max_K: int = 6) -> None:
    """
    演示 C(A_K) 随 K 增大趋近于2
    """
    print(f"{'K':>3} | {'|A|':>8} | {'|A+A|':>10} | {'|A-A|':>10} | {'C(A)':>10}")
    print("-" * 50)
    
    for K in range(1, max_K + 1):
        A = construct_hyra_family(K, 0.01)
        A_set = set(A[:min(len(A), 2000)])  # 控制规模用于演示
        C = compute_exponent(A_set)
        
        sumset = compute_sumset(A_set)
        diffset = compute_diffset(A_set)
        
        print(f"{K:>3} | {len(A_set):>8} | {len(sumset):>10} | {len(diffset):>10} | {C:>10.6f}")


if __name__ == "__main__":
    # 演示构造
    A_small = [1, 2, 4, 8, 16, 32]
    print(f"示例集合 A = {A_small}")
    print(f"|A| = {len(A_small)}")
    print(f"|A+A| = {len(compute_sumset(set(A_small)))}")
    print(f"|A-A| = {len(compute_diffset(set(A_small)))}")
    print(f"C(A) = {compute_exponent(set(A_small)):.6f}")
    print()
    
    print("Convergence demonstration (simplified):")
    demonstrate_convergence(5)

// hyra_construction.go
// Hyra核心构造的高性能Go实现
// 用于大规模集合的和差集计算

package main

import (
	"fmt"
	"math"
	"math/big"
)

// ChineseRemainder 实现中国剩余定理
func ChineseRemainder(remainders []int64, moduli []int64) int64 {
	M := int64(1)
	for _, m := range moduli {
		M *= m
	}

	result := int64(0)
	for i, a := range remainders {
		Mi := M / moduli[i]
		// 计算 Mi 在模 moduli[i] 下的逆元
		inv := modInverse(Mi, moduli[i])
		result = (result + a*Mi*inv) % M
	}

	return result
}

// modInverse 计算模逆元 (扩展欧几里得算法)
func modInverse(a, m int64) int64 {
	g, x, _ := extendedGCD(a, m)
	if g != 1 {
		return 0 // 逆元不存在
	}
	return (x%m + m) % m
}

// extendedGCD 扩展欧几里得算法
func extendedGCD(a, b int64) (int64, int64, int64) {
	if b == 0 {
		return a, 1, 0
	}
	g, x1, y1 := extendedGCD(b, a%b)
	return g, y1, x1 - (a/b)*y1
}

// Base12Digit 十二进制数字结构
type Base12Digit struct {
	Digits []int8 // 每个位置的值 0-11
	Length int
}

// NewBase12Number 从整数创建十二进制表示
func NewBase12Number(value int64) *Base12Digit {
	digits := make([]int8, 0)
	for value > 0 {
		digits = append(digits, int8(value%12))
		value /= 12
	}
	return &Base12Digit{
		Digits: digits,
		Length: len(digits),
	}
}

// ToInt64 将十二进制表示转回整数
func (b *Base12Digit) ToInt64() int64 {
	result := int64(0)
	base := int64(1)
	for _, d := range b.Digits {
		result += int64(d) * base
		base *= 12
	}
	return result
}

// Subtract 计算十二进制差（带借位分析）
func (b *Base12Digit) Subtract(other *Base12Digit) (*Base12Digit, int) {
	maxLen := b.Length
	if other.Length > maxLen {
		maxLen = other.Length
	}

	result := make([]int8, maxLen)
	borrowCount := 0
	borrow := int8(0)

	for i := 0; i < maxLen; i++ {
		a := int8(0)
		if i < b.Length {
			a = b.Digits[i]
		}
		bb := int8(0)
		if i < other.Length {
			bb = other.Digits[i]
		}

		diff := a - bb - borrow
		if diff < 0 {
			diff += 12
			borrow = 1
			borrowCount++
		} else {
			borrow = 0
		}
		result[i] = diff
	}

	return &Base12Digit{Digits: result, Length: maxLen}, borrowCount
}

// SumsetCalculator 和差集计算器
type SumsetCalculator struct {
	Elements    []int64
	ElementSet  map[int64]bool
	SumCache    map[int64]bool
	DiffCache   map[int64]bool
}

// NewSumsetCalculator 创建新的计算器
func NewSumsetCalculator(elements []int64) *SumsetCalculator {
	elementSet := make(map[int64]bool)
	for _, e := range elements {
		elementSet[e] = true
	}
	return &SumsetCalculator{
		Elements:   elements,
		ElementSet: elementSet,
		SumCache:   make(map[int64]bool),
		DiffCache:  make(map[int64]bool),
	}
}

// ComputeSumset 计算和集
func (sc *SumsetCalculator) ComputeSumset() []int64 {
	for _, a := range sc.Elements {
		for _, b := range sc.Elements {
			sc.SumCache[a+b] = true
		}
	}

	result := make([]int64, 0, len(sc.SumCache))
	for k := range sc.SumCache {
		result = append(result, k)
	}
	return result
}

// ComputeDiffset 计算差集
func (sc *SumsetCalculator) ComputeDiffset() []int64 {
	for _, a := range sc.Elements {
		for _, b := range sc.Elements {
			sc.DiffCache[a-b] = true
		}
	}

	result := make([]int64, 0, len(sc.DiffCache))
	for k := range sc.DiffCache {
		result = append(result, k)
	}
	return result
}

// ComputeExponent 计算 C(A) = log σ(A) / log δ(A)
func (sc *SumsetCalculator) ComputeExponent() float64 {
	n := float64(len(sc.Elements))
	sumset := sc.ComputeSumset()
	diffset := sc.ComputeDiffset()

	sigma := float64(len(sumset)) / n
	delta := float64(len(diffset)) / n

	if sigma <= 1 || delta <= 1 {
		return 0
	}

	return math.Log(sigma) / math.Log(delta)
}

// CRTAdditiveBasis CRT加法基构造
type CRTAdditiveBasis struct {
	Moduli   []int64
	Bases    [][]int64
	Combined []int64
}

// NewCRTAdditiveBasis 创建CRT加法基
func NewCRTAdditiveBasis(moduli []int64, basisSize int) *CRTAdditiveBasis {
	cb := &CRTAdditiveBasis{
		Moduli: moduli,
		Bases:  make([][]int64, len(moduli)),
	}

	// 在每个循环群上构造对称加法基
	for i, m := range moduli {
		base := make([]int64, 0, 2*basisSize)
		for j := int64(1); j <= int64(basisSize); j++ {
			base = append(base, j%m)
			base = append(base, (-j)%m)
		}
		cb.Bases[i] = base
	}

	// 通过CRT组合
	cb.combine()

	return cb
}

// combine 通过CRT组合所有基
func (cb *CRTAdditiveBasis) combine() {
	// 递归组合所有可能
	cb.combineRecursive(0, make([]int64, len(cb.Moduli)))
}

func (cb *CRTAdditiveBasis) combineRecursive(depth int, current []int64) {
	if depth == len(cb.Moduli) {
		element := ChineseRemainder(current, cb.Moduli)
		cb.Combined = append(cb.Combined, element)
		return
	}

	for _, v := range cb.Bases[depth] {
		current[depth] = v
		cb.combineRecursive(depth+1, current)
	}
}

// HyraFamily 构造Hyra集合族
func HyraFamily(K int, epsilon float64) []int64 {
	// 十二进制数字子集
	digitSubset := []int8{0, 1, 4, 5, 8, 9}

	// 生成十二进制核心
	core := make([]int64, 0)
	generateBase12(&core, digitSubset, K, 0, 0)

	// CRT模数
	moduli := []int64{
		int64(2*K + 1),
		int64(3*K + 1),
	}
	// 确保互质
	if gcd(moduli[0], moduli[1]) != 1 {
		moduli[1] = int64(5*K + 1)
	}

	basisSize := int(math.Log(float64(K)) * 2)
	if basisSize < 1 {
		basisSize = 1
	}

	crtBasis := NewCRTAdditiveBasis(moduli, basisSize)

	// 组合
	scale := int64(math.Pow(12, float64(K+1)))
	result := make([]int64, 0)
	for _, c := range core {
		crtLen := len(crtBasis.Combined)
		limit := crtLen
		if K < limit {
			limit = K
		}
		for i := 0; i < limit; i++ {
			result = append(result, c+scale*crtBasis.Combined[i])
		}
	}

	return result
}

// generateBase12 递归生成十二进制数字序列
func generateBase12(result *[]int64, digits []int8, length int, pos int, current int64) {
	if pos == length {
		*result = append(*result, current)
		return
	}
	for _, d := range digits {
		generateBase12(result, digits, length, pos+1, current*12+int64(d))
	}
}

func gcd(a, b int64) int64 {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

// BigIntSumset 大整数和集计算（用于超大集合）
func BigIntSumset(elements []*big.Int) []*big.Int {
	seen := make(map[string]bool)
	result := make([]*big.Int, 0)

	for _, a := range elements {
		for _, b := range elements {
			sum := new(big.Int).Add(a, b)
			key := sum.String()
			if !seen[key] {
				seen[key] = true
				result = append(result, sum)
			}
		}
	}

	return result
}

func main() {
	fmt.Println("=== Hyra Core Construction: Base-12 + CRT ===")
	fmt.Println()

	// 演示小规模构造
	K := 3
	A := HyraFamily(K, 0.01)
	fmt.Printf("K=%d, |A|=%d\n", K, len(A))
	fmt.Printf("前10个元素: ")
	for i := 0; i < 10 && i < len(A); i++ {
		fmt.Printf("%d ", A[i])
	}
	fmt.Println()

	// 计算和差集指数
	calc := NewSumsetCalculator(A)
	exponent := calc.ComputeExponent()
	fmt.Printf("C(A) = %.6f\n", exponent)

	// 十二进制减法演示
	fmt.Println("\n--- Base-12 Subtraction Analysis ---")
	a := NewBase12Number(157) // 157 = 111 (base 12)
	b := NewBase12Number(85)  // 85  = 71  (base 12)
	fmt.Printf("157 in base-12: %v\n", a.Digits)
	fmt.Printf("85  in base-12: %v\n", b.Digits)
	diff, borrows := a.Subtract(b)
	fmt.Printf("Difference: %v, Borrow count: %d\n", diff.Digits, borrows)
	fmt.Printf("Diff value: %d\n", diff.ToInt64())

	// 大整数演示
	fmt.Println("\n--- Big Integer Sumset ---")
	bigElems := []*big.Int{
		big.NewInt(1),
		big.NewInt(12),
		big.NewInt(144),
		big.NewInt(1728),
	}
	sumset := BigIntSumset(bigElems)
	fmt.Printf("BigInt sumset size: %d\n", len(sumset))
}

"""
验证脚本：检查Hyra构造的数学性质
"""

import sys
import math
import random
from typing import Set, List, Tuple


def verify_sum_diff_inequality(A: Set[int]) -> bool:
    """
    验证和差集不等式 σ(A)^{1/2} ≤ δ(A) ≤ σ(A)^2
    """
    n = len(A)
    sumset = set()
    diffset = set()
    
    for a in A:
        for b in A:
            sumset.add(a + b)
            diffset.add(a - b)
    
    sigma = len(sumset) / n
    delta = len(diffset) / n
    
    lower_bound = math.sqrt(sigma) - 1e-10
    upper_bound = sigma ** 2 + 1e-10
    
    return lower_bound <= delta <= upper_bound


def check_monotonic_convergence(constructor, K_values: List[int]) -> List[float]:
    """
    检查 C(A_K) 是否随 K 单调递增趋近于2
    """
    exponents = []
    for K in K_values:
        A = constructor(K)
        A_set = set(A[:min(len(A), 5000)])
        C = compute_exponent(A_set)
        exponents.append(C)
        print(f"K={K}: |A|={len(A_set)}, C(A)={C:.6f}")
    
    # 检查单调性
    for i in range(1, len(exponents)):
        if exponents[i] < exponents[i-1] - 0.01:
            print(f"WARNING: Non-monotonic at K={K_values[i]}")
    
    return exponents


def compute_exponent(A: Set[int]) -> float:
    """计算 C(A)"""
    n = len(A)
    sumset = set()
    diffset = set()
    
    for a in A:
        for b in A:
            sumset.add(a + b)
            diffset.add(a - b)
    
    sigma = len(sumset) / n
    delta = len(diffset) / n
    
    if sigma <= 1 or delta <= 1:
        return 0.0
    
    return math.log(sigma) / math.log(delta)


def random_search_benchmark(trials: int = 1000, max_size: int = 100) -> float:
    """
    随机搜索基准测试：随机集合能达到的最好指数
    """
    best = 0.0
    best_set = None
    
    for t in range(trials):
        size = random.randint(10, max_size)
        A = set(random.sample(range(0, 10000), size))
        C = compute_exponent(A)
        if C > best:
            best = C
            best_set = A
    
    print(f"随机搜索 {trials} 次最佳结果: C(A) = {best:.6f}")
    return best


def main():
    print("=" * 60)
    print("Hyra 构造正确性验证")
    print("=" * 60)
    
    # 测试1: 基本不等式验证
    print("\n[测试1] 和差集不等式验证")
    test_sets = [
        {1, 2, 3, 4, 5},
        {1, 3, 5, 7, 9},
        {1, 2, 4, 8, 16},
        set(range(0, 50, 3)),
    ]
    for i, A in enumerate(test_sets):
        ok = verify_sum_diff_inequality(A)
        C = compute_exponent(A)
        sigma = len(set(a+b for a in A for b in A)) / len(A)
        delta = len(set(a-b for a in A for b in A)) / len(A)
        print(f"  集合{i+1}: C={C:.6f}, σ={sigma:.4f}, δ={delta:.4f}, 不等式={'✓' if ok else '✗'}")
    
    # 测试2: 随机搜索对比
    print("\n[测试2] 随机搜索基准")
    random_search_benchmark(500, 50)
    
    # 测试3: 十二进制结构分析
    print("\n[测试3] 十二进制差集分析")
    from collections import Counter
    
    # 构造同一数字和不同数字的差分布
    base = 12
    digits = [0, 1, 4, 5, 8, 9]
    
    same_diff = Counter()
    cross_diff = Counter()
    
    for d1 in digits:
        for d2 in digits:
            diff = (d1 - d2) % base
            if d1 == d2:
                same_diff[diff] += 1
            else:
                cross_diff[diff] += 1
    
    print(f"  同一数字的差分布: {len(same_diff)} 种不同值")
    print(f"  不同数字的差分布: {len(cross_diff)} 种不同值")
    print(f"  差集压缩比: {len(cross_diff) / (len(digits)**2):.4f}")
    
    print("\n" + "=" * 60)
    print("验证完成")
    print("=" * 60)


if __name__ == "__main__":
    main()