# P2638: Sparsest degree-600 recurrence for a prime-indicator prefix

- ID: `P2638`
- Reference: `prime-indicator-recurrence-weight-600`
- Page: https://theoremdb.org/statements/P2638
- Record maturity: Reviewed problem with recorded work

## Problem

Let \(s_i=1\) when \(i+2\) is prime and \(s_i=0\) otherwise, for \(0\le i<1024\). Minimize the Hamming weight of \(c=(c_0,\ldots,c_{600})\in\mathbb F_2^{601}\) subject to \(c_0=c_{600}=1\) and \(\sum_{j=0}^{600}c_js_{i+j}=0\) for every \(0\le i<424\).

### Problem setup

- **Remark.** The vector c is a finite binary connection polynomial for the given prefix.
- **Definition.** Hamming weight is the number of nonzero coefficients.

### What counts as a solution

- Give a feasible coefficient vector of minimum weight and an exact lower-bound certificate for the affine binary system.

## Status

Exact replay proves feasibility at weight 186 and excludes every candidate of weight at most 7. [1](#reference-1)

## Work

### Evidence for the current status

**Computation 1 (The minimum tap weight lies between 8 and 186).** Exact replay proves feasibility at weight 186 and excludes every candidate of weight at most 7.

Write
\[
 v_j=(s_j,s_{j+1},\ldots,s_{j+423})\in\mathbf F_2^{424}.
\]
Since the endpoint coefficients are fixed at one, an internal tap set \(T\subseteq\{1,\ldots,599\}\) is feasible exactly when
\[
 \bigoplus_{j\in T}v_j=v_0\oplus v_{600}.
\]
The exact verifier forms all 599 internal columns and all 179,101 pairwise xor values. It tests internal subsets of sizes zero through four with singleton and pair tables. For size five, it checks all 35,641,099 triples against the pair table. If the two sides of one of these table identities share an index, cancellation gives a smaller solution already excluded. The sweep finds no solution with at most five internal taps. Every admissible vector has two endpoint taps, so its total weight is at least 8.

For the upper bound, interpret the hexadecimal integer
```
104020000042401000000000000100000010004020001702093a81120945a122179a133c52f6f5d7860361026a5b18b00f8b704122171b46d22ccedce3191b108a19415c43e921a850ae209
```
with coefficient \(c_j\) in bit \(j\), starting at the least significant bit. It has 601 bits, both endpoint bits are one, and its Hamming weight is 186. Exact substitution gives zero violations among all 424 recurrence equations.

Row reduction of the 424 recurrence rows together with the two endpoint rows gives rank 426 and affine dimension 175. The exact minimum inside the certified interval
\[
8\leq w_{\min}\leq186
\]
remains open. A two-minute pseudo-Boolean solver probe at threshold 150 ended without a model or an unsatisfiability proof and contributes no further bound.

### Background and intake notes

The affine system has many solutions, so the hard part is a finite minimum-distance computation rather than recurrence existence.

- Original intake status: Status remains unverified. Sparse recurrences for arithmetic indicator sequences are studied, while this exact prefix and degree may be new.
- Row-reduce the 426 constraints once, then solve minimum weight in the resulting affine coset by information-set decoding, SAT, or integer programming.
- Trap: Berlekamp-Massey minimizes degree rather than coefficient weight. A recurrence with a smaller degree can still be denser under this fixed-degree convention.

- Recorded example: A weight-186 incumbent is encoded by hex 104020000042401000000000000100000010004020001702093a81120945a122179a133c52f6f5d7860361026a5b18b00f8b704122171b46d22ccedce3191b108a19415c43e921a850ae209.

### Prior approaches

- **Route 1** (supported): Classical shift-register synthesis minimizes register length, while this candidate asks for minimum weight in one affine binary coset. [1](#reference-1) [2](#reference-2) [3](#reference-3)

### Runnable artifacts

- **Artifact 1** (reproduced): A four-second standard-library program certifies rank 426, the interval 8 to 186, and hashes the complete constraint data. [1](#reference-1)

### Computational notes

- Exact GF(2) elimination gave rank 426 and affine dimension 175. A seeded 500000-step nullspace walk started at weight 227 and ended at 186; endpoint bits and all 424 recurrence equations were replayed with zero violations.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `prime-indicator-recurrence-weight-600`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>J. Massey, “Shift-register synthesis and BCH decoding”. IEEE Transactions on Information Theory 15(1) (1969), 122-127. DOI 10.1109/TIT.1969.1054260. James L. Massey, Shift-register synthesis and BCH decoding, IEEE Transactions on Information Theory 15(1), 1969, pages 122-127; Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. A. van Tilborg, On the inherent intractability of certain coding problems, IEEE Transactions on Information Theory 24(3), 1978, pages 384-386; Arne Winterhof, Pseudorandom binary sequences: quality measures and number-theoretic constructions, IEICE Transactions on Fundamentals E106.A(12), 2023, pages 1452-1460 https://doi.org/10.1109/TIT.1969.1054260
   - Also cited at IEEE Transactions on Information Theory 15(1), 1969, pages 122-127
   - Also cited at Exact standard-library computation in pirw600-artifact-subset-and-incumbent-certificate, executed on 2026-07-25
   - Also cited at Inline CPython standard-library exhaustive computation executed on 2026-07-25
   - scholarly_publication; reference source; checked 2026-08-01
   - Source use: citation_only
   - For Sparsest degree-600 recurrence for a prime-indicator prefix, the reviewed source scope is James L. Massey, Shift-register synthesis and BCH decoding, IEEE Transactions on Information Theory 15(1), 1969, pages 122-127; Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. A. van Tilborg, On the inherent intractability of certain coding problems, IEEE Transactions on Information Theory 24(3), 1978, pages 384-386; Arne Winterhof, Pseudorandom binary sequences: quality measures and number-theoretic constructions, IEICE Transactions on Fundamentals E106.A(12), 2023, pages 1452-1460. The packet makes no inference beyond that cited scope.
   - Source named by the research packet.
2. <a id="reference-2"></a>E. Berlekamp, R. McEliece, and H. van Tilborg, “On the inherent intractability of certain coding problems (Corresp.)”. IEEE Transactions on Information Theory 24(3) (1978), 384-386. DOI 10.1109/TIT.1978.1055873. IEEE Transactions on Information Theory 24(3), 1978, pages 384-386 https://doi.org/10.1109/TIT.1978.1055873
   - scholarly_publication; reference source; checked 2026-08-01
   - Source use: citation_only
   - For Sparsest degree-600 recurrence for a prime-indicator prefix, the reviewed source scope is IEEE Transactions on Information Theory 24(3), 1978, pages 384-386. The packet makes no inference beyond that cited scope.
3. <a id="reference-3"></a>Arne WINTERHOF, “Pseudorandom Binary Sequences: Quality Measures and Number-Theoretic Constructions”. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E106.A(12) (2023), 1452-1460. DOI 10.1587/transfun.2023SDI0001. IEICE Transactions on Fundamentals E106.A(12), 2023, pages 1452-1460 https://doi.org/10.1587/transfun.2023SDI0001
   - scholarly_publication; reference source; checked 2026-08-01
   - Source use: citation_only
   - For Sparsest degree-600 recurrence for a prime-indicator prefix, the reviewed source scope is IEICE Transactions on Fundamentals E106.A(12), 2023, pages 1452-1460. The packet makes no inference beyond that cited scope.