Iteration 9
RetrieveGate decision
RetrieveReasoningAdditional evidence would help identify better sequence constructions, optimization methods, or relevant bounds for this correlation-minimization problem. No reusable search documents are available, so a fresh search is…
Additional evidence would help identify better sequence constructions, optimization methods, or relevant bounds for this correlation-minimization problem. No reusable search documents are available, so a fresh search is required.
Knowledge before this stepThe latest full rewrite substantially improved the measured combined score to 2.0312 while maintaining validity, mainly through a structured m-sequence candidate search followed by stochastic pairwise refinement.…
The latest full rewrite substantially improved the measured combined score to 2.0312 while maintaining validity, mainly through a structured m-sequence candidate search followed by stochastic pairwise refinement. Earlier attempts were slower and had a worse c5 value. However, the search database contains no documents or prior queries, and the remaining challenge—finding a lower maximum non-cyclic overlap under box and sum constraints—is unresolved. It is unclear whether the current heuristic is near-optimal, whether stronger constructions or mathematical bounds exist, or how to reduce evaluation time without sacrificing quality.
Population analysis
📊 State: The retained population contains 11 programs, with scores from 1.9890529190 to 2.5938350971 and a current parent at the retained maximum of 2.5938350971.
Key Numbers:
• Score spread: the worst score is 1.9890529190, the best is 2.5938350971, and the population standard deviation is 0.2228693338.
• Central tendency: the mean score is 2.1221045135, while the median is 2.0312491758.
• Score diversity: 7 unique scores occur among 11 programs; the score 2.0312495307 appears 3 times.
• Trajectory: scores rise from 1.9890529190 at iteration 0 to 2.5938350971 at iteration 8, including a final parent-to-child increase of 0.5625855665.
Patterns Observed:
• Parent selection: 10 parent-selection slots used 6 unique IDs; the most selected parent appeared 4 times, representing 0.4 of parent selections, and had score 1.9890529190.
• Context selection: 13 context-selection slots involved 7 unique IDs; the most selected context appeared 3 times, with a reported most-selected-program fraction of 0.75.
• Outcomes: 7 retained rows were marked “improved”, 3 were marked “unchanged” or otherwise not improved at the row level, and the largest recorded delta was 0.5625855665.
Query · round 1
optimal balanced binary sequences minimum maximum aperiodic cross-correlation with complement low overlap
Find mathematical constructions or bounds for minimizing the maximum non-cyclic overlap between a balanced length-64 sequence and its complement, potentially improving on the current m-sequence plus stochastic pairwise refinement.
Query rationale
The current program relies on heuristic m-sequence candidates and annealing, but it does not establish whether better structured sequences or known low-correlation constructions exist. Literature on balanced binary, Barker, and complementary sequences may provide stronger candidate patterns, provable lower bounds, or efficient deterministic search methods that can replace or guide the expensive stochastic refinement under the box and exact-sum constraints.
What this round establishedThe documents reinforce that balanced binary and related low-autocorrelation constructions are promising, especially Rudin-Shapiro, Legendre, Sidelnikov, Galois, and optimized low-PSL sequences. The strongest directly…
The documents reinforce that balanced binary and related low-autocorrelation constructions are promising, especially Rudin-Shapiro, Legendre, Sidelnikov, Galois, and optimized low-PSL sequences. The strongest directly actionable lead is testing a length-64 Rudin-Shapiro-style initialization or other optimized binary sequence before continuous pairwise refinement. The binary correlation literature also provides lower-bound and optimality concepts, but much of the evidence concerns cyclic autocorrelation or cross-correlation rather than this program's maximum non-cyclic overlap with the complement, so the objective correspondence remains incomplete. No document supplies an explicit length-64 sequence proven optimal for the exact box-and-sum problem, nor does it establish whether fractional amplitudes outperform binary candidates. These constructions still need implementation and evaluator testing, along with measurement of runtime and post-projection feasibility effects.
Kept-document mean prediction 2.64167
Query · round 2
explicit optimized balanced binary sequence length 64 minimum maximum aperiodic correlation with complement Rudin-Shapiro PSL
Find an explicit length-64 balanced or near-balanced binary sequence optimized for maximum non-cyclic overlap with its complement, together with its ordering and objective value, rather than relying on the current m-sequence initialization and stochastic refinement.
Query rationale
The current program's best candidate is built from a length-63 m-sequence with an inserted value, while the strongest evidence points toward optimized Rudin-Shapiro or other low-PSL sequences. Existing documents discuss related autocorrelation and periodic metrics but do not provide a concrete length-64 sequence or establish correspondence to this evaluator's non-cyclic complement-overlap objective. An explicit optimized sequence could be implemented directly, benchmarked against the current 2.5938350971 result, and used as a stronger deterministic starting point for pairwise refinement.
What this round establishedThe new documents strengthen the case for testing length-64 balanced binary constructions, especially minimum-PSL sequences and Rudin-Shapiro/Golay-Rudin-Shapiro recurrences. Evidence_7 is the most actionable because it…
The new documents strengthen the case for testing length-64 balanced binary constructions, especially minimum-PSL sequences and Rudin-Shapiro/Golay-Rudin-Shapiro recurrences. Evidence_7 is the most actionable because it indicates that balanced 64-bit sequences with minimum PSL are known, although the retrieved excerpt does not provide an explicit sequence to copy. Evidence_6 confirms that optimized Rudin-Shapiro sequences are studied at powers-of-two lengths including 64, but likewise does not provide the actual optimized bits. Evidence_8 and evidence_10 provide implementable Rudin-Shapiro definitions and recurrences, while evidence_9 supplies theoretical complementary-pair and cross-correlation results. The current program instead starts from a custom 63-bit m-sequence with one inserted value and then performs continuous pairwise refinement, so none of these candidates has yet been tested in the exact evaluator. The main remaining knowledge gap is the correspondence between PSL/autocorrelation or cross-correlation metrics and this program's maximum non-cyclic overlap with the complement. Additional untested implementation work is needed: generate balanced length-64 Rudin-Shapiro, Golay-Rudin-Shapiro, and minimum-PSL binary candidates, evaluate them directly, and compare binary initialization against fractional amplitudes and refinement. Runtime and the effect of the final projection also remain to be measured.
Kept-document mean prediction 2.675
Query · round 3
"balanced 64-bit" "minimum PSL" binary sequence coefficients download
Find the explicit bit pattern or supplementary data/code for a minimum-PSL balanced binary sequence of length 64, rather than only a claim that such sequences exist.
Query rationale
The current program relies on an inserted m-sequence plus continuous refinement and scores 2.5938, while the strongest evidence predicts about 2.675 from a known balanced 64-bit minimum-PSL construction. The missing bit pattern is the key unresolved implementation detail; obtaining it would allow direct evaluation under this program's complement-overlap objective and comparison against fractional refinement.
What this round establishedThe new documents further confirm that length-64 balanced binary sequences with minimum peak sidelobe level exist, and that exhaustive-search and optimized Rudin-Shapiro methods are relevant candidate sources. However,…
The new documents further confirm that length-64 balanced binary sequences with minimum peak sidelobe level exist, and that exhaustive-search and optimized Rudin-Shapiro methods are relevant candidate sources. However, the documents do not provide explicit 64-bit coefficients, so they do not yet enable direct reproduction of a stronger candidate. The optimized Rudin-Shapiro material suggests a potentially useful initialization, while the binary PSL optimization procedure provides a possible implementation direction, but its objective is not identical to the evaluator's maximum non-cyclic overlap with the complement and includes notation intended for broader or complex-valued code optimization. The current program still relies on a custom inserted m-sequence followed by continuous refinement, so the key remaining work is untested implementation: obtain or reconstruct explicit balanced 64-bit minimum-PSL and optimized Rudin-Shapiro sequences, evaluate them directly, and test whether PSL improvements transfer to the evaluator. The effects of binary versus fractional initialization, refinement, projection, and runtime also remain unknown.
Kept-document mean prediction 2.675
Evidence sent to the solver
optimal balanced binary sequences minimum maximum aperiodic cross-correlation with complement low overlap
explicit optimized balanced binary sequence length 64 minimum maximum aperiodic correlation with complement Rudin-Shapiro PSL
"balanced 64-bit" "minimum PSL" binary sequence coefficients download
Knowledge after searchThe new documents further confirm that length-64 balanced binary sequences with minimum peak sidelobe level exist, and that exhaustive-search and optimized Rudin-Shapiro methods are relevant candidate sources. However,…
The new documents further confirm that length-64 balanced binary sequences with minimum peak sidelobe level exist, and that exhaustive-search and optimized Rudin-Shapiro methods are relevant candidate sources. However, the documents do not provide explicit 64-bit coefficients, so they do not yet enable direct reproduction of a stronger candidate. The optimized Rudin-Shapiro material suggests a potentially useful initialization, while the binary PSL optimization procedure provides a possible implementation direction, but its objective is not identical to the evaluator's maximum non-cyclic overlap with the complement and includes notation intended for broader or complex-valued code optimization. The current program still relies on a custom inserted m-sequence followed by continuous refinement, so the key remaining work is untested implementation: obtain or reconstruct explicit balanced 64-bit minimum-PSL and optimized Rudin-Shapiro sequences, evaluate them directly, and test whether PSL improvements transfer to the evaluator. The effects of binary versus fractional initialization, refinement, projection, and runtime also remain unknown.
Stop: search budget exhausted
Web sources
Predictions are model estimates before evaluation.
www.researchgate.netThe Cross-Correlation of Binary Sequences With Optimal ...
two balanced binary sequences with optimal cross-correlation have the minimal maximum autocorrelation magnitude as well.
math.uni-paderborn.deSequences with Small Correlation
It follows from Lemma 2.1.1 and the identity (2.2) that an optimal binary sequence A of length n cannot be balanced if n is congruent to 0 or 1 modulo 4. Therefore, every balanced binary sequence A of length n > 1 satisfies (2.4) max 0<u<n|Ru(A)| ≥ 1 for n ≡3 (mod 4) 2 for n ≡2 (mod 4) 3 for n ≡1 (mod 4) 4 for n ≡0 (mod 4). 4 KAI-UWE SCHMIDT If A is a balanced binary sequence of length n > 1 for which equality holds in (2.4), then we say that A is optimal balanced. We now show that optimal balanced binary sequences exist …
www.semanticscholar.org[PDF] The Cross-Correlation of Binary Sequences With Optimal Autocorrelation | Semantic Scholar
Skip to search formSkip to main contentSkip to account menu Optimal Autocorrelation and Cross-Correlation Yang YangXiaohu Tang Computer Science, Engineering IEEE Communications Letters 2014 TLDR The maximum cross-correlation magnitude of a balanced quaternary sequence pair of period N with the maximum out-of-phase autocorrelation magnitude √5, where N = 4f + 1 is a prime and f is an odd integer, is shown to be √N, achieving one of the new lower bounds.Expand 9 Save ### Binary Sequences With Three-Valued Cross Correlations of Different Lengths Jin-Quan Luo Mathematics IEEE Transactions on Information Theory 2016 TLDR [...] 1 1 Excerpt Save ### [Nearly optimal balanced quaternary sequence pairs of prime period N≡5(mod8)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{docume]( Mengzhen …
www.preprints.orgBinary Sequences with Low Aperiodic Autocorrelations
Image 17 and the optimized sequence ($B_{o p t}^{L e g}$). Conjecture 5 shows that $$ \frac{d \left(\right. B_{i n i t}^{L e g} , B_{o p t}^{L e g} \left.\right)}{n} \approx 0.01 , $$ [...] The length of the Rudin–Shapiro sequence is $n = 2^{m}$ and the optimization process is performed on the same length, i.e., without any truncation. We denote the initial and optimized Rudin–Shapiro sequences as $B_{i n i t}^{R S}$ and $B_{o p t}^{R S}$, respectively. [...] In practice, we prefer binary sequences that have a lower PSL value and a higher F value. From a computational standpoint, optimization based on the merit factor (2) differs significantly from optimization based on PSL (3). In the former, …
langevin.univ-tln.frBest Pair of Binary Sequences
f(T) = sum\_{k} f(k) T^k We have two products : f(T) f( 1/T ) = sum\_{k} A\_k(f) T^k and f(T) f( 1/T ) = sum\_{k} C\_k(f) T^k modulo (T^n - 1) The coefficients C\_k(f) are nothing but the autocorrelation values of f, the A\_k(f) are called aperiodic correlation values. A sequence with A\_k(f) smaller than one in absolute (for k>0) is called a Barker sequence. Such sequences could be useful for radar applications but one conjectures the non existence of Barker sequences of length greater than 13. A sequence with C\_k(f) equals to zero for all k>0 is called perfect, one conjectures the non existence of such combinatorial object for n>4. It is easy to see that C\_k(f) = n …
www.preprints.orgBinary Sequences with Low Aperiodic Autocorrelations
| m | $\mathbf{\mathit{n}} = 2^{\mathbf{\mathit{m}}}$ | LB | UB | PSL | ---: ---: | 10 | 1024 | 60 | 104 | 85 | | 11 | 2048 | 100 | 172 | 153 | | 12 | 4096 | 166 | 286 | 217 | | 13 | 8192 | 275 | 475 | 373 | | 14 | 16,384 | 457 | 789 | 557 | | 15 | 32,768 | 768 | 1309 | 961 | | 16 | 65,536 | 1257 | 2172 | 1717 | | 17 | 131,072 | 2086 | 3604 | 2445 | | 18 | 262,144 | 3461 | 5779 | 4285 | | 19 | 524,288 | 5743 …
www.researchgate.netBinary Sequences With Small Peak Sidelobe Level
All balanced 64-bit minimum PSL codes are presented, and the upper limit on known consecutive lengths to have PSL = 4 codes is extended to 70.
en.wikipedia.orgRudin–Shapiro sequence - Wikipedia
Let : {\displaystyle {\tilde {\epsilon }}_{k}(n)={\begin{cases}\epsilon _{k}(n)&{\text{if }}k\leq N-1,\\\epsilon _{0}(n)&{\text{if }}k=N.\end{cases}}} Then let : {\displaystyle u(n,N)=\sum _{0\leq k<N}{\tilde {\epsilon }}_{k}(n){\tilde {\epsilon }}_{k+1}(n).} Finally, let : {\displaystyle S(N,x)=\sum _{0\leq n<2^{N}}\exp(2\pi ixu(n,N)).} [...] : {\displaystyle \sup _{x\in \mathbb {R} }\left|\sum _{0\leq n<N}r_{n}e^{inx}\right|\leq C{\sqrt {N}}.} It is conjectured that one can take {\displaystyle C={\sqrt {6}}}, but while it is known that {\displaystyle C\geq {\sqrt {6}}}, the best published upper bound is currently {\displaystyle C\leq (2+{\sqrt {2}}){\sqrt {3/5}}}. Let {\displaystyle P_{n}} be the n-th Shapiro polynomial. Then, when {\displaystyle N=2^{n}-1}, the above inequality gives a bound on {\displaystyle \sup _{x\in \mathbb {R} }|P_{n}(e^{ix})|}. More recently, bounds have also been given for the magnitude of the coefficients of {\displaystyle |P_{n}(z)|^{2}} where {\displaystyle |z|=1}. Shapiro arrived …
par.nsf.govPeak Sidelobe Level and Peak Crosscorrelation of Golay
CORRELATION OF GOLAY–RUDIN–SHAPIRO SEQUENCES 3 Observe that xn and yn are polynomials of degree less than ℓn for each nonnegative integer n, and that they are of degree precisely ℓn−1 if deg(y0) = ℓ0 −1, so that the nth Rudin–Shapiro sequence and its companion are bi-nary sequences of length 2n. For binary sequences, Golay indicates in [Gol51, p. 469] (and formally proves in [Gol61, pp. 84–85]) that each step of his con-struction always produces a new complementary pair from an existing one, so that every pair (xn, yn) produced by this construction is a complementary pair. See [KM21, Construction 6.1] for a proof that generalizes this result to work for all sequences with complex terms. We want to investigate the …
faculty.nps.edu1. Short primer on Golay-Rudin-Shapiro sequence - Faculty
Now, since fn+1 = fngn, then, using the induction hypothesis and the expression for gn, we get fn+1(x) = ¯ x1fn(x2, . . . , xn+1) ⊕x1gn(x2, . . . , xn+1) = ¯ x1 X i≥2,j−i≥2 xixj ⊕ n X k=3 sk(x2, . . . , xn+1) 8 ⊕x1 n X i=3 xi ⊕ n X i=2 xixi+1 ! , which by expansion and simplification, renders the claim on the ANF of fn+1. [...] Proof. fn be the Boolean function on n variables whose truth table are 2n consecutive bits bi, 0 ≤i ≤2n −1. Using equation (1.1), we immediately see that the function fn along with a companion function gn (defined below) satisfy the …
www.researchgate.netBinary Sequences with Minimum Peak Sidelobe Level up ...
All balanced 64-bit minimum PSL codes are presented, and the upper limit on known consecutive lengths to have PSL = 4 codes is extended to 70. In addition
www.researchgate.netEfficient exhaustive search for optimal-peak-sidelobe ...
All balanced 64-bit minimum PSL codes are presented, and the upper limit on known consecutive lengths to have PSL = 4 codes is extended to 70.
cdn.intechopen.comA Survey on the Design of Binary Pulse Compression ...
70. Also they searched all 64-bit sequences and found all MPSL codes and exhibited all balanced ones in a table. It is the longest power of two codes that have been fully searched (Coxson & Russo, 2004). Next, Levanon and Mozeson provided a summary of optimal PSLs for lengths up to 69 (Levanon & Mozeson, 2004). In 2006, Ferrara described an integer programming method for generating low autocorrelation binary codes at arbitrary bit lengths. He compared PSL values and MFs (for bit length 71 through 100) of the sequences obtained with this method to the best literature-based minimal-PSL sequences and compiled a table of best minimum-PSL binary sequences for bit lengths 71 through 100. His record of length 74 was …
www.preprints.orgBinary Sequences with Low Aperiodic Autocorrelations
| m | $\mathbf{\mathit{n}} = 2^{\mathbf{\mathit{m}}}$ | LB | UB | PSL | ---: ---: | 10 | 1024 | 60 | 104 | 85 | | 11 | 2048 | 100 | 172 | 153 | | 12 | 4096 | 166 | 286 | 217 | | 13 | 8192 | 275 | 475 | 373 | | 14 | 16,384 | 457 | 789 | 557 | | 15 | 32,768 | 768 | 1309 | 961 | | 16 | 65,536 | 1257 | 2172 | 1717 | | 17 | 131,072 | 2086 | 3604 | 2445 | | 18 | 262,144 | 3461 | 5779 | 4285 | | 19 | 524,288 | 5743 …
www.eurasip.org[PDF] Design of Binary Sequences with Low PSL/ISL - EURASIP
Algorithm 2 Binary Code Entry Optimization Input: Initial code vector x(n), code entry d and θ; Output: Optimal solution x⋆ d; 1) Set for all k = 1, . . . , N −1 • adk = x(n) d+k1A(d + k) + x(n) d−k1A(d −k) and cdk = PN−k i=1,i̸=d,d−k x(n) i x(n) i+k; • ζdk = [adk, cdk]T and νdk = |FFT(ζdk)|2; 2) Calculate uk = θνT dk + (1 −θ) PN−1 l=1 νT dl ∈R2, k = 1, . . . , N −1 and ωd = [max{u1}, max{u2}}]T ; 3) Find the index i⋆where ωd is minimum; 4) Set x⋆ d = eφ⋆ d with φ⋆ d = π(i⋆−1). [...] TABLE I PSL AND ISL OF “PARETO-OPTIMAL” …
No recorded documents for this selection.
04Code & measured result
8 candidate attemptsFull rewrite
Code diff recorded excerpt+149−119
- return float(np.max(np.correlate(h, 1.0 - h, mode="full")) * (2.0 / len(h)))+ return float(np.max(np.correlate(h, 1.0 - h, mode="full")) * (2.0 / n))- sequence = 2.0 * np.asarray(bits, dtype=np.float64) - 1.0+ base = np.concatenate([bits, np.asarray([extra], dtype=np.int8)])+ current = np.asarray(start, dtype=np.float64).copy()+ temperature = 0.012 * (1.0 - it / iterations) + 0.00025+ accept = rng.random() < np.exp((score - new_score) / temperature)+def _continuous_refine(start, rng, iterations=260000):- if current[i] <= 1e-12 and current[j] >= 1.0 - 1e-12:- temperature = 0.0018 * (1.0 - iteration / 70000.0) + 0.000015- accept = rng.random() < np.exp((current_score - new_score) / temperature)- interior = np.flatnonzero((h > 1e-12) & (h < 1.0 - 1e-12))- k = int(interior[np.argmin(np.abs(h[interior] - 0.5))])- raise ValueError("h_values contain NaN or inf values")
