{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R111",
  "content_hash": null,
  "slug": "cbf11-claim-exact-maximum-44",
  "type": "claim",
  "title": "The exact maximum is C(11) = 44",
  "summary": "A 44-word construction and two published exact searches establish the value 44.",
  "relevance": "This records a result, observation, or conjecture used to assess the target problem.",
  "relevance_source": "derived",
  "body": "The answer is\n\\[\nC(11)=44.\n\\]\nChee, 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.\n\nA compact construction is\n\\[\nA=\\{0001u1:u\\in\\{0,1\\}^{6}\\text{ and }u\\text{ contains no }000\\}.\n\\]\nThe 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.\n\nThe same certificate independently replays the later integer upper bound. Proposition 10 writes the maximum as\n\\[\nS(2,11)=\\max\\sum_{i=1}^{10}x_i y_{11-i},\n\\]\nwhere \\(x_1=y_1=1\\) and\n\\[\nx_i+y_i=\\sum_{j=1}^{i-1}x_jy_{i-j}.\n\\]\nTheorem 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.",
  "status": "established",
  "evidence_grade": "reproduced",
  "scope": {
    "kind": "bounded",
    "statement": "binary cross-bifix-free codes whose words all have length 11",
    "bounds": {
      "alphabet_size": {
        "min": 2,
        "max": 2
      },
      "word_length": {
        "min": 11,
        "max": 11
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://arxiv.org/abs/1209.0236v2",
      "locator": "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"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/1209.0236v2",
    "locator": "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"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R110",
      "title": "Exact construction check and 640-state upper certificate",
      "object_type": "artifact",
      "relation": "verifies",
      "direction": "incoming"
    },
    {
      "slug": "cross-bifix-free-binary-eleven",
      "title": "cross bifix free binary eleven",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}