{"id":"47d3acf5-ae0d-4b91-9526-a540c9ccd456","arxiv_id":"2412.09904","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The Hamming graph H(4t-1, 2t) has quantum chromatic number exactly 4t, with exact product values for related families.","lead":"This paper finds a new infinite family of graphs, the Hamming graphs H(4t-1, 2t), whose quantum chromatic number is exactly known: 4t colors. Exact quantum chromatic numbers are rare, so this gives researchers new test cases for quantum advantage in graph coloring games.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.2's lower bound rests on an eigenvalue-ordering inequality that is false as stated; the strict comparison |ρ(4j+2)|/|ρ(4j-2)| < 1 fails at the boundary, so λ_min = -C(4t-1,2t)/(4t-1) is not rigorously established.","rationale":"The paper's central new claim is the exact quantum chromatic number of H_{4t-1,2t}. The lower-bound half of the proof depends entirely on identifying λ_min via the eigenvalue ordering after equation (28). The reader's weakest-assumption analysis pinpointed exactly this step, and independent calculation confirms the problem: the strict inequality |ρ(4j+2)|/|ρ(4j-2)| < 1 is false at the boundary, e.g., t = 2, j = 1 gives ratio 1. This is not a cosmetic issue: the text asserts a complete ordering of negative eigenvalues on the basis of a false inequality and then falls back on symmetry without a full check. However, the theorem itself appears salvageable: the upper-bound projectors are explicit and valid, the eigenvalue formulas (22) are correct, small cases in the tables match the claimed minimum, and the ratio can likely be made correct by restricting the comparison range and treating symmetric pairs separately. The product corollaries then follow from cited lemmas. Therefore the appropriate action is to keep the conditional verdict: the mathematics is probably right, but the proof of the load-bearing eigenvalue-minimum step must be completed and the false strict inequality corrected. I agree with the reader's identification; no additional independent objection surfaced.","tokens_in":16447,"tokens_out":12937,"duration_ms":121480,"concrete_test":"Compute the full spectrum of H_{4t-1,2t} in exact rational arithmetic using formula (22) for t = 2, 3, 4, ..., 20, and confirm in every case that min_r ρ(r) = -C(4t-1,2t)/(4t-1). In particular, for t = 2 verify that |ρ(6)|/|ρ(2)| = 1, which refutes the strict inequality as stated, and then check that the minimum is nonetheless attained at r = 1, 2. If any t yields a negative eigenvalue with magnitude exceeding C(4t-1,2t)/(4t-1), the lower bound in Theorem 3.2 collapses; otherwise the concern is a proof gap, not a false theorem, and the corrected ordering argument should be supplied.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The exact determination χ_q(H_{4t-1,2t}) = 4t hinges on the spectral lower bound χ_q ≥ 1 + λ_max/|λ_min|, and therefore on the claim that the most negative eigenvalue is ρ(1) = ρ(2) = -C(4t-1,2t)/(4t-1). The proof of this in Section 3.2.1, immediately after equation (28), compares ratios of negative eigenvalues. The first ratio, |ρ(4j+2)|/|ρ(4j+1)| = 1, is correct. The second, |ρ(4j+2)|/|ρ(4j-2)| < 1 for 1 ≤ j ≤ floor(t/2), is not always strict: for t = 2 (n = 7, ℓ = 4), direct computation gives ρ(1) = ρ(2) = ρ(6) = -5, so |ρ(6)|/|ρ(2)| = 1, not < 1. The same equality occurs at the boundary j = floor(t/2) when t is even. The proof then asserts the ordering of negative eigenvalues and invokes symmetry, but the false strict inequality means the ordering is not established for all j by the argument given. If some unexamined eigenvalue had larger magnitude, the lower bound χ_q ≥ 4t would fail. The theorem may be true and repairable — for instance by comparing only r ≤ (4t-1)/2 and using ρ(r) = ρ(n-r) — but as written the proof contains a real gap in the load-bearing step.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies quantum chromatic numbers of Hamming graphs H_{n,ℓ} = Cay(F_2^n, S), where S is the set of weight-ℓ vectors. It first reproves the known result χ_q(H_n) = n for Hadamard graphs H_n with n = 4t using Krawtchouk polynomials. The main new result, Theorem 3.2, claims that for n = 4t−1 and ℓ = 2t the spectrum of H_{n,ℓ} has the explicit form in (22) and that χ_q(H_{n,ℓ}) = n+1 = 4t, with the lower bound obtained from Lemma 2.4 and the upper bound from an explicit 4t-color quantum coloring. The paper also gives a general upper bound χ_q(H_{n,ℓ}) ≤ 2ℓ for ℓ ≥ n/2 (Theorem 3.4), bounds for H_{4t+2,2t+2} (Proposition 3.5), and exact values for products of such graphs (Theorem 3.10).","tokens_in":16728,"tokens_out":20366,"duration_ms":174885,"significance":"If the main theorem is fully established, it provides a new infinite family of graphs—other than complete graphs, cycles, bipartite graphs, and Hadamard graphs—whose quantum chromatic numbers are exactly determined. The upper bound is an explicit quantum coloring, and the spectral formulas are derived from standard Krawtchouk identities and group characters with no fitted parameters, which are strengths of the paper. The product results are natural corollaries of the main theorem and known spectral bounds. The significance of the paper depends on a correct and complete proof of the spectral claim in Theorem 3.2.","major_comments":[{"comment":"The proof that λ_min = ρ(1) relies on the strict inequality |ρ(4j+2)|/|ρ(4j−2)| < 1 for 1 ≤ j ≤ ⌊t/2⌋, but this inequality is not always strict: for t = 4 and j = 2, and also for t = 2 and j = 1, the ratio equals 1. Since Eq. (29) derives the lower bound χ_q ≥ 4t from the asserted value of λ_min, this is a load-bearing gap in the argument as written. The theorem is likely true and the gap is repairable, e.g., by restricting to r ≤ (4t−1)/2, using the symmetry ρ(r) = ρ(n−r), and proving a non-strict comparison that still shows every negative eigenvalue has magnitude at most |ρ(1)|; the authors must supply this corrected argument.","section":"Section 3.2.1, after Eq. (28)"},{"comment":"The lower bound ℓ ≤ χ_q(H_{4t+2,2t+2}) depends on the assertion \"It is a routine to check that λ_min = −C(n,ℓ)/(2t+1)\", but no verification is provided. In light of the eigenvalue-ordering error in Theorem 3.2, this step cannot be left as a routine check; the authors should either prove the eigenvalue ordering for this case or give a precise reference where the spectrum and its minimum eigenvalue are established.","section":"Section 3.2.2, Proposition 3.5"}],"minor_comments":[{"comment":"There are several typographical errors: \"Krawchouk\" should be \"Krawtchouk\" (e.g., in the abstract and Eq. (6)), \"shcems\" appears in Section 1, \"Menamara\" and \"Mcnamara\" are used inconsistently for the same reference, and \"unite vector\" and \"orthnormal\" appear in Section 2.1.1.","section":"Throughout"},{"comment":"The transition from Eq. (17) to the claim that λ_min = −C(n,n/2)/(n−1) is described as \"easy to see\" without a monotonicity argument for the sequence in (17); a short justification would make the reproof of the Hadamard-graph result self-contained.","section":"Section 3.1"},{"comment":"The notation Kℓ(r) is introduced without specifying the parameters n and q, which can be confusing because Krawtchouk polynomials depend on n and q; the authors should write K_{n,q}^ℓ(r) or explicitly state the suppressed parameters.","section":"Section 2.5, Eq. (15)"},{"comment":"References [12] and [16] are incomplete (no journal or publisher details, only arXiv identifiers); the authors should update them to the published versions if they exist.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The main theorem's gap is real but localized and likely fixable; I did not find evidence of circularity or unsupported optimism beyond the eigenvalue-ordering issue. If the authors repair the proof of λ_min in Theorem 3.2 and provide the missing verification in Proposition 3.5, the paper should be publishable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one if you care about exact quantum chromatic numbers. The new result is Theorem 3.2: for n = 4t-1, l = 2t, the Hamming graph H_{n,l} over F2 has chi_q = n+1 = 4t. That gives a second infinite family with exact values, after the Hadamard graphs, and the product corollaries follow cleanly from known lemmas. The upper bound uses explicit projectors that are easy to verify, and the spectral formula via Krawtchouk polynomials is clean. The soft spot is the lower bound. The proof that lambda_min = -C(4t-1,2t)/(4t-1) contains a strict inequality that is not always strict. Specifically, |rho(4j+2)|/|rho(4j-2)| < 1 is claimed for 1 <= j <= floor(t/2); at t = 2 the ratio is 1 for j = 1 (rho(6) = rho(2) = -5). The ordering of negative eigenvalues is then asserted with strict inequalities that can be equalities. So the spectral lower bound chi_q >= 4t is not rigorously established by the text. Small cases check out, and the gap is repairable: replace the strict comparison with <= and handle the boundary, or use the symmetry rho(r) = rho(n-r) to restrict r <= (n-1)/2. But as written the load-bearing step is incomplete. Proposition 3.5 has the same issue, with the eigenvalue check dismissed as routine. The literature claim that this is only the second known family rests on 'as far as we know' plus a Chinese survey; a proper survey citation would strengthen that. The typos (Krawchouk, 'shcems') are cosmetic. Overall: the mathematics is likely right, and the paper deserves a serious referee. Send it to review, but ask for a complete proof of the eigenvalue ordering in Theorem 3.2 and for Proposition 3.5 to be written out. The main theorem is a real addition to a sparse literature.","headline":"A genuinely new exact quantum chromatic number family with a repairable gap in the spectral lower-bound proof; worth refereeing.","tokens_in":624,"tokens_out":2415,"would_cite":true,"duration_ms":67485,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05E30","94B25","97K30"],"pacs":[],"model":"deepseek-v4-flash","headline":"For n=4t−1 and distance 2t, the Hamming graph has quantum chromatic number exactly n+1.","keywords":["quantum chromatic number","chromatic number","quantum colouring","Hamming graphs","Krawtchouk polynomials","spectral lower bound","Hadamard graphs"],"falsifier":"One could compute the numbers ρ(r) from equations (26)–(27) for a fixed t, say t=3 (n=11, ℓ=6), and compare all negative values with −\\binom{11}{6}/11; if any is smaller, the claimed quantum chromatic number is wrong. A direct check of the ordering step for all j up to ⌊t/2⌋ would settle whether the proof's inequality is strict where it needs to be.","tokens_in":16194,"feed_emoji":"🎨","tokens_out":8571,"duration_ms":88066,"temperature":0.7,"pith_summary":"The paper determines the quantum chromatic number of a family of Hamming graphs, where vertices are binary strings and edges join strings at a fixed Hamming distance. Its main result is that for n=4t−1 and distance ℓ=2t, the graph H_{n,ℓ} has quantum chromatic number exactly 4t = n+1. This is only the second infinite family, beyond the Hadamard graphs, whose quantum chromatic number is exactly known. The value matters because quantum coloring can use fewer colors than classical coloring, and explicit examples of that phenomenon are rare. The paper also proves bounds for Hamming graphs with ℓ ≥ n/2 and exact values for products of these graphs.","feed_headline":"Hamming graphs with 4t−1 bits need exactly 4t quantum colors","feed_subtitle":"A spectral bound plus an explicit coloring settles the value, joining Hadamard graphs as the only known families.","key_machinery":"The machinery has four pieces: the Hamming graph H_{n,ℓ}, whose vertices are strings in F_2^n and whose edges join strings at Hamming distance ℓ; Krawtchouk polynomials, which turn the eigenvalue problem into coefficient extraction from (1−x)^ℓ(1+x)^{n−ℓ}; the spectral lower bound χ_q ≥ 1 + λ_max/|λ_min|; and an explicit projection-valued coloring constructed from the same phases used for Hadamard graphs, taken in dimension 2ℓ. The product theorem uses the observation that when both factors saturate the spectral bound, the product's quantum chromatic number is the minimum of the two factors' values.","core_discovery":"The central discovery is Theorem 3.2: for the Cayley graph H_{4t−1,2t} on $F_2^{{4t−1}}$ with edges between vectors at Hamming distance 2t, the quantum chromatic number is χ_q = 4t = n+1. The proof computes the full spectrum using Krawtchouk polynomials: the eigenvalue attached to a vector of weight r is given by two closed binomial formulas, and the minimum eigenvalue is −\\binom{4t−1}{2t}/(4t−1). The spectral lower bound χ_q ≥ 1 + λ_max/|λ_min| then gives 4t, and an explicit set of 4t projections on $C^{{4t}}$, built by embedding each vertex into V_{4t} with a zero last coordinate, provides a valid quantum coloring, so the bound is tight.","pith_inferences":["A natural next test is the range 2ℓ < n, which the paper leaves open: one could run the same spectral computation to get a lower bound and look for a coloring dimension smaller than 2ℓ.","If the classical chromatic number of H_{4t−1,2t} can be shown to exceed 4t, these graphs would exhibit quantum advantage; the paper does not prove such a gap.","The embedding trick of adding one zero coordinate suggests a broader construction: any Hamming graph with ℓ ≥ n/2 can be quantum-colored with 2ℓ colors, so the exact boundary case is a special case where the spectrum and the coloring match."],"forward_implications":["Every t ≥ 1 gives a new graph on 4t−1 bits whose quantum chromatic number is exactly 4t, forming a second infinite family alongside Hadamard graphs.","Because χ_q(H) ≤ χ(H), each of these graphs has classical chromatic number at least 4t = n+1.","For n=4t+2 and ℓ=2t+2, the quantum chromatic number lies between ℓ and 2ℓ, with the upper bound coming from an explicit coloring into dimension 2ℓ.","Products such as H_{4t,2t} × H_{4s,2s} have quantum chromatic number equal to the smaller of the two factors when both factors saturate the spectral bound.","The spectrum of H_{n,ℓ} admits closed binomial formulas whenever n−2ℓ is small, which is what makes the exact values and bounds accessible."],"supporting_citations":[{"why":"Supplies the spectral lower bound χ_q ≥ 1 + λ_max/|λ_min| used to derive the value 4t.","marker":"[4]"},{"why":"Provides the Krawtchouk polynomial identities used to evaluate the eigenvalues of H_{n,ℓ}.","marker":"[11]"},{"why":"Gives the explicit quantum coloring of Hadamard graphs that the paper adapts to color H_{4t−1,2t}.","marker":"[12]"},{"why":"Gives the upper bound for quantum chromatic numbers of graph products used in Theorem 3.10.","marker":"[16]"},{"why":"Supplies the representation-theoretic eigenvalue formula for normal Cayley graphs used to start the spectrum computation.","marker":"[17]"}],"fun_headline_variants":["New family: exact quantum colors for Hamming graphs","For 4t-1-bit Hamming graphs, quantum colors = n+1","Second known family with explicit quantum chromatic numbers","Hamming scheme graphs: quantum colors determined exactly","Quantum chromatic number of Hamming graph H(4t-1,2t) is 4t"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower bound 4t rests on identifying the most negative eigenvalue of H_{4t−1,2t} as the one attached to vectors of weight 1 and 2; if some other eigenvalue were more negative, the claimed quantum chromatic number would be too low.","fun_headline_variants_meta":{"raw":{"variants":["New family: exact quantum colors for Hamming graphs","For 4t-1-bit Hamming graphs, quantum colors = n+1","Second known family with explicit quantum chromatic numbers","Hamming scheme graphs: quantum colors determined exactly","Quantum chromatic number of Hamming graph H(4t-1,2t) is 4t"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002052,"raw_usage":{"total_tokens":7949,"prompt_tokens":864,"completion_tokens":7085,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":480,"completion_tokens_details":{"reasoning_tokens":6995}},"tokens_in":480,"tokens_out":7085,"duration_ms":54645,"temperature":1.0,"reasoning_tokens":6995,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:36:46.232824+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"One could compute the numbers ρ(r) from equations (26)–(27) for a fixed t, say t=3 (n=11, ℓ=6), and compare all negative values with −\\binom{11}{6}/11; if any is smaller, the claimed quantum chromatic number is wrong. A direct check of the ordering step for all j up to ⌊t/2⌋ would settle whether the proof's inequality is strict where it needs to be.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the spectral lower bound χ_q ≥ 1 + λ_max/|λ_min| used to derive the value 4t."},{"cited_title":"Levenshtein, Krawtchouk polynomials and universal b ounds for codes and designs in Hamming spaces, IEEE Trans","cited_arxiv_id":null,"evidence_quote":"Provides the Krawtchouk polynomial identities used to evaluate the eigenvalues of H_{n,ℓ}."},{"cited_title":"Menamara, ArXiv: 2410","cited_arxiv_id":null,"evidence_quote":"Gives the explicit quantum coloring of Hadamard graphs that the paper adapts to color H_{4t−1,2t}."},{"cited_title":"Steinberg, Representation Theory of Finite Groups: An Int roductory Approach","cited_arxiv_id":null,"evidence_quote":"Supplies the representation-theoretic eigenvalue formula for normal Cayley graphs used to start the spectrum computation."}],"review_version":1}