File size: 7,596 Bytes
2facf1f | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 | """
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}")
|