[#P100019] Maximum cross-bifix-free binary code of length 11

Contents

Problem. What is the largest size \(C(11)\) of a set of binary words of length \(11\) such that no nonempty proper prefix of any codeword equals a suffix of any codeword, including the same codeword?

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

1Remarks

Remark 1. The condition is imposed for every ordered pair of codewords and every overlap length 1 through 10.

Remark 2. Such sets are also called non-overlapping or cross-bifix-free codes.

2What counts as a solution

Give a code and a matching upper-bound certificate establishing C(11).

1Status

Saved packet · July 24, 2026

What counts as a solution

Saved solution (The exact maximum is C(11) = 44). A 44-word construction and two published exact searches establish the value 44.^[2][1]

Verification

The answer is \[ C(11)=44. \] Chee, Kiah, Purkayastha, and Wang list 44 at \(n=11\), attained by their construction with parameter \(k=3\). Their Section III-A explains the upper certificate: the vertices are all bifix-free binary words of length \(n\), two vertices are adjacent when the words are mutually cross-bifix-free, and MaxCliqueDyn computes the largest clique. Table I marks 44 as optimal. Stanovnik, Moškon, and Mraz later reproduce \(S(2,11)=44\) in Table 1 and state that their values through length 16 agree with Chee et al.

A compact construction is \[ A=\{0001u1:u\in\{0,1\}^{6}\text{ and }u\text{ contains no }000\}. \] The number of six-bit words avoiding \(000\) is the tribonacci value 44. The executable certificate generates all of them and checks each of the \(44^2\cdot10=19{,}360\) ordered prefix-suffix comparisons.

The same certificate independently replays the later integer upper bound. Proposition 10 writes the maximum as \[ S(2,11)=\max\sum_{i=1}^{10}x_i y_{11-i}, \] where \(x_1=y_1=1\) and \[ x_i+y_i=\sum_{j=1}^{i-1}x_jy_{i-j}. \] Theorem 15 permits an optimum with \(x_i y_i=0\) for \(i>11/2\). Exhausting every choice through \(i=5\), followed by the two zero-side choices at each later level, produces 640 terminal states. Their largest objective is 44. This gives a short replay of the exact upper bound.

1Packet records

Show recorded summaries

Record	Kind	Assessment
A 44-word construction and two published exact searches establish the value 44.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
claim · Computation 1 A 44-word construction and two published exact searches establish the value 44.^[2][1] Relevance to this problem This records a result, observation, or conjecture used to assess the target problem. Evidence ReproducedA replay is recorded for this computation. Inspect the replay record for its procedure and scope. Record state established Scope binary cross-bifix-free codes whose words all have length 11 Sources Reference 2, Reference 1 Details The answer is \[ C(11)=44. \] Chee, Kiah, Purkayastha, and Wang list 44 at \(n=11\), attained by their construction with parameter \(k=3\). Their Section III-A explains the upper certificate: the vertices are all bifix-free binary words of length \(n\), two vertices are adjacent when the words are mutually cross-bifix-free, and MaxCliqueDyn computes the largest clique. Table I marks 44 as optimal. Stanovnik, Moškon, and Mraz later reproduce \(S(2,11)=44\) in Table 1 and state that their values through length 16 agree with Chee et al. A compact construction is \[ A=\{0001u1:u\in\{0,1\}^{6}\text{ and }u\text{ contains no }000\}. \] The number of six-bit words avoiding \(000\) is the tribonacci value 44. The executable certificate generates all of them and checks each of the \(44^2\cdot10=19{,}360\) ordered prefix-suffix comparisons. The same certificate independently replays the later integer upper bound. Proposition 10 writes the maximum as \[ S(2,11)=\max\sum_{i=1}^{10}x_i y_{11-i}, \] where \(x_1=y_1=1\) and \[ x_i+y_i=\sum_{j=1}^{i-1}x_jy_{i-j}. \] Theorem 15 permits an optimum with \(x_i y_i=0\) for \(i>11/2\). Exhausting every choice through \(i=5\), followed by the two zero-side choices at each later level, produces 640 terminal states. Their largest objective is 44. This gives a short replay of the exact upper bound. Open full record →
Standard-library Python verifies the 44 codewords, constructs the 568-vertex compatibility graph, and exhausts the reduced integer program.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 Standard-library Python verifies the 44 codewords, constructs the 568-vertex compatibility graph, and exhausts the reduced integer program.^[1] Relevance to this problem This supplies a computation, dataset, or executable check used to assess the target problem. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope all binary words of length 11 and every reduced SQN(2,11) state supplied by Theorem 15 Sources Reference 1 Entry point `join source_lines with newline and run with python3` Runtime CPython 3, standard library only Details The program scans all 2,048 binary words and finds 568 unbordered vertices. Their mutual-compatibility graph has 48,708 edges. It generates the 44 words \(0001u1\), sorts them, confirms their SHA-256 digest, and tests every ordered pair at every proper overlap length. For the upper bound it implements Proposition 10 exactly. At levels \(i=2,3,4,5\), every integer \(x_i\) between zero and \(x_i+y_i\) is retained. At levels 6 through 10, Theorem 15 reduces the choices to the endpoints, since one of \(x_i,y_i\) can be zero in a maximum solution. The state counts after levels 1 through 10 are \[ 1,2,4,8,20,40,80,160,320,640. \] Four terminal sequences attain 44, and every other terminal sequence has a smaller objective. The canonical compact JSON output has SHA-256 digest `dbbd9e77f6aaf955a2c40086c8f6e83d3fca75dcaf47fb0aebf9c23893dc17bc`. Related: Computation 1 Open full record →
No records match these filters.

Notes and companion material

Current rigorous bounds are 44 <= C(11) <= 97. The upper bound is the disjoint-shift count floor(2^11/(2*11-1)).

Original intake status. Status unknown. Cross-bifix-free codes are well studied and C(11) may already be published.

After discarding bordered words, the problem is maximum clique in a 568-vertex compatibility graph.
Complement and bit reversal are graph automorphisms. Fixing a lexicographically least codeword should remove duplicate branches.

Recorded example 1. A recoverable 44-word code is {0001u1 : u is a six-bit word containing no occurrence of 000}.

Computational notes

There are exactly 44 six-bit words avoiding 000. An exact verifier generated the resulting 44 codewords and checked every ordered codeword pair at each overlap length 1 through 10. Exact maximum-clique search had previously certified C(n)=1,1,2,3,5,8,14,24 for 3 <= n <= 10.

How the 2 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemMaximum cross-bifix-free binary code of length 11

All 1 recorded relations between these records and the problem

Exact construction check and 640-state upper certificate verifies The exact maximum is C(11) = 44

2See also

A 368-word code in the fifth strong power of the 7-cyclecoding theory
VT zero-syndrome weight log-concavity through length 2000coding theory
Hamming covering radius of the zero-syndrome VT codecoding theory

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Maximum cross-bifix-free binary code of length 11.” TheoremDB. P100019. Problem statement; statement text SHA-256 d86cb6ae0d841ceede71e38a559d12761f5238ffbaf844e8a074d748757af860. https://theoremdb.org/statement/?ref=P100019

BibTeX

@misc{theoremdb-problem-d86cb6ae0d841ceede71e38a559d12761f5238ffbaf844e8a074d748757af860,
  title = {{Maximum cross-bifix-free binary code of length 11}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 d86cb6ae0d841ceede71e38a559d12761f5238ffbaf844e8a074d748757af860},
  url = {https://theoremdb.org/statement/?ref=P100019}
}

Plain text: Built Markdown snapshot

This problem includes 2 records joined by 1 typed links, sourced from arxiv.org^[2], current as of July 24, 2026.

1Lean verification

Lean formalization needed

A solution has been submitted and awaits independent review.

Open TheoremDB Researcher

Upload a Lean project archive

Once Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.

1References

2 entries have incomplete source metadata. Each affected row names the fields that still need editorial review.

Lidija Stanovnik, Miha Moškon, Miha Mraz, In search of maximum non-overlapping codes, 2024. Proposition 10, Theorem 15, Section 6, and Table 1. ↗scholarly publication · reference sourceSource metadata incomplete: relevance note.Source use: citation only.
Packet source. Yeow Meng Chee, Han Mao Kiah, Punarbasu Purkayastha, and Chengmin Wang, Cross-Bifix-Free Codes Within a Constant Factor of Optimality, IEEE Transactions on Information Theory 59 (2013), 4668-4674, Section III-A, Table I and the maximum-clique paragraph on page 4671; independently replayed in cbf11-artifact-code-and-sqn-certificate. ↗preprint · reference source · arXiv:1209.0236v2 · checked 2026-07-24Source metadata incomplete: publication-style citation.Source use: citation only.Source named by the research packet.

Finite code-optimization target with an explicit incumbent and a reproducible compatibility graph.

Discussion

Loading discussion.

[#P100019] Maximum cross-bifix-free binary code of length 11

1Remarks

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Remarks

2What counts as a solution

1StatusSolution submittedNot Lean-verified

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance

1Status