ccevolve/tx_workspace/ac1/sparse_support.py

"""
Try functions with specific sparse support patterns.

Key insight: The autocorrelation inequality is related to additive combinatorics.
For a set S, the autoconvolution (1_S * 1_S)(t) counts pairs (a,b) in S with a+b=t.
To minimize max(f*f)/(∫f)², we want the "sumset" S+S to be as uniformly distributed as possible.

This is related to:
- B_h sets (Sidon sets)
- Difference sets
- Constructions from finite fields

Let me try constructions inspired by these.
"""
import numpy as np
from scipy.optimize import minimize
import time

def compute_c1_fft(f_values, dx):
    f = np.maximum(f_values, 0.0)
    N = len(f)
    M = 2 * N
    fft_f = np.fft.rfft(f, n=M)
    conv = np.fft.irfft(fft_f * fft_f, n=M) * dx
    integral_sq = (np.sum(f) * dx) ** 2
    if integral_sq < 1e-20:
        return 1e10
    return float(np.max(conv) / integral_sq)

def compute_c1_smooth_and_grad(f, N, dx, alpha=200.0):
    M = 2 * N
    fft_f = np.fft.rfft(f, n=M)
    conv = np.fft.irfft(fft_f * fft_f, n=M) * dx
    integral = np.sum(f) * dx
    if integral < 1e-15:
        return 1e10, np.zeros(N)
    integral_sq = integral ** 2
    max_val = np.max(conv)
    shifted = conv - max_val
    mask = shifted > -50.0 / alpha
    weights = np.zeros_like(conv)
    weights[mask] = np.exp(alpha * shifted[mask])
    sum_w = np.sum(weights)
    if sum_w < 1e-30:
        weights[np.argmax(conv)] = 1.0
        sum_w = 1.0
    smooth_max = max_val + np.log(sum_w) / alpha
    softmax_w = weights / sum_w
    c1 = smooth_max / integral_sq
    fft_sw = np.fft.rfft(softmax_w, n=M)
    fft_fp = np.fft.rfft(f, n=M)
    corr = np.fft.irfft(fft_sw * np.conj(fft_fp), n=M)
    grad_f = 2.0 * corr[:N] * dx / integral_sq - 2.0 * smooth_max * dx / (integral**3)
    return c1, grad_f

def full_opt(f_init, N, dx, maxiter=3000):
    params = np.sqrt(np.maximum(f_init, 0.0) + 1e-12)
    for alpha in [0.5, 2.0, 10.0, 100.0, 1000.0, 10000.0, 100000.0]:
        def obj(p, a=alpha):
            f = p ** 2
            c1, g = compute_c1_smooth_and_grad(f, N, dx, a)
            return c1, g * 2 * p
        result = minimize(obj, params, jac=True, method='L-BFGS-B',
                         options={'maxiter': maxiter, 'ftol': 1e-16, 'gtol': 1e-15})
        params = result.x
    f_out = params ** 2
    return f_out, compute_c1_fft(f_out, dx)

N = 2000
dx = 0.5 / N

# 1. Quadratic residue construction
# For prime p, the quadratic residues mod p form a set with nice autocorrelation
print("=== Quadratic Residue Sets ===")
for p in [7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]:
    qr = set()
    for a in range(p):
        qr.add((a * a) % p)
    # Map to [0, N)
    f = np.zeros(N)
    for r in qr:
        # Fill blocks corresponding to quadratic residues
        block_start = int(r * N / p)
        block_end = int((r + 1) * N / p)
        f[block_start:block_end] = 1.0
    c1_raw = compute_c1_fft(f, dx)
    f_opt, c1_opt = full_opt(f, N, dx)
    if c1_opt < 1.51:
        print(f"  p={p}: raw C1={c1_raw:.6f}, optimized C1={c1_opt:.10f} ***")
    elif p <= 31 or c1_opt < 1.515:
        print(f"  p={p}: raw C1={c1_raw:.6f}, optimized C1={c1_opt:.10f}")

# 2. Paley-type construction
print("\n=== Paley-type ===")
for p in [23, 29, 31, 37, 41, 43, 47]:
    # Legendre symbol
    leg = np.zeros(p)
    for a in range(1, p):
        leg[a] = 1 if pow(a, (p-1)//2, p) == 1 else -1

    # Use (1 + legendre)/2 as indicator
    indicator = (1 + leg) / 2

    # Map to function
    f = np.zeros(N)
    for i in range(p):
        block_start = int(i * N / p)
        block_end = int((i + 1) * N / p)
        f[block_start:block_end] = indicator[i]

    f_opt, c1 = full_opt(f, N, dx)
    print(f"  p={p}: C1 = {c1:.10f}")

# 3. Perfect difference sets
# A (v, k, λ) difference set gives each difference exactly λ times
# Known constructions: Singer, Hall, ...
print("\n=== Difference Sets ===")

# Singer difference set for PG(2,q)
# Parameters: v = q² + q + 1, k = q + 1, λ = 1
# For q=2: v=7, k=3, λ=1 → {0,1,3}
# For q=3: v=13, k=4, λ=1 → {0,1,3,9}
# For q=4: v=21, k=5, λ=1 → {0,1,5,11,13}
# For q=5: v=31, k=6, λ=1

diff_sets = {
    7: [0, 1, 3],  # (7,3,1)
    13: [0, 1, 3, 9],  # (13,4,1)
    21: [0, 1, 5, 11, 13],  # (21,5,1) - Singer
    31: [0, 1, 3, 8, 12, 18],  # (31,6,1)
    57: [0, 1, 3, 13, 32, 36, 43, 52],  # (57,8,1)
    73: [0, 1, 3, 7, 15, 31, 36, 54, 63],  # (73,9,1)
    91: [0, 1, 3, 9, 27, 49, 56, 61, 77, 81],  # (91,10,1)
}

for v, D in diff_sets.items():
    f = np.zeros(N)
    for d in D:
        block_start = int(d * N / v)
        block_end = int((d + 1) * N / v)
        f[block_start:block_end] = 1.0

    c1_raw = compute_c1_fft(f, dx)
    f_opt, c1 = full_opt(f, N, dx)
    print(f"  ({v},{len(D)},1): raw={c1_raw:.6f}, opt={c1:.10f}")

# 4. Multi-scale construction: union of sets at different scales
print("\n=== Multi-scale ===")
for n_scales in [2, 3, 4, 5]:
    for seed in range(5):
        np.random.seed(seed * 100 + n_scales)
        f = np.zeros(N)
        for scale in range(n_scales):
            block_size = N // (3 ** (scale + 1))
            if block_size < 1:
                break
            n_blocks = N // block_size
            # Random selection of blocks
            selected = np.random.rand(n_blocks) > 0.5
            for i in range(n_blocks):
                if selected[i]:
                    s = i * block_size
                    e = min(s + block_size, N)
                    f[s:e] += 1.0 / (scale + 1)

        f_opt, c1 = full_opt(f, N, dx)
        if c1 < 1.51:
            print(f"  scales={n_scales}, seed={seed}: C1 = {c1:.10f} ***")
        elif seed == 0:
            print(f"  scales={n_scales}, seed={seed}: C1 = {c1:.10f}")

# 5. Cantor-set like construction (middle-third removal at multiple levels)
print("\n=== Fractal constructions ===")
for removal_frac in [1/3, 1/4, 1/5, 2/5, 1/2]:
    for levels in [1, 2, 3, 4, 5]:
        f = np.ones(N)
        for level in range(levels):
            block_size = N // (int(1/removal_frac) + 1) ** (level + 1)
            if block_size < 1:
                break
            n_blocks = N // block_size
            for b in range(n_blocks):
                # Remove middle fraction of each block
                start = b * block_size
                mid_start = start + int(block_size * (1 - removal_frac) / 2)
                mid_end = start + int(block_size * (1 + removal_frac) / 2)
                if mid_end <= N:
                    f[mid_start:mid_end] = 0.0

        c1_raw = compute_c1_fft(f, dx)
        f_opt, c1 = full_opt(f, N, dx)
        if c1 < 1.515:
            print(f"  remove={removal_frac:.2f} levels={levels}: raw={c1_raw:.4f}, opt={c1:.10f}")

# 6. Concatenation of optimized small solutions
print("\n=== Tiling approach ===")
# Find best at small N, then tile it
for N_small in [50, 100, 200]:
    dx_small = 0.5 / N_small
    best_c1_small = np.inf
    best_f_small = None

    for seed in range(100):
        np.random.seed(seed + 7000)
        f_init = np.abs(np.random.randn(N_small)) + 0.1
        f_opt, c1 = full_opt(f_init, N_small, dx_small, maxiter=1000)
        if c1 < best_c1_small:
            best_c1_small = c1
            best_f_small = f_opt

    print(f"  Best at N={N_small}: C1 = {best_c1_small:.10f}")

    # Tile to N=2000
    repeats = N // N_small
    f_tiled = np.tile(best_f_small, repeats)[:N]
    c1_tiled = compute_c1_fft(f_tiled, dx)
    f_opt_tiled, c1_opt_tiled = full_opt(f_tiled, N, dx)
    print(f"    Tiled raw: C1 = {c1_tiled:.10f}, optimized: C1 = {c1_opt_tiled:.10f}")