Alphabeta Math
CounterexampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck pass
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Strict asymptotic separation need not give zero finite-block error

Statement refuted

For every finite IID source and finite DMC, if H(PS)<ρC(W), then every finite blocklength ratio n/k=ρ admits a deterministic joint code with zero block error.

Facts & Assumptions

Given: A uniform binary IID source, a BSC with crossover probability 1/4, channel blocklength nk=6k, and a deterministic joint code as in Finite-alphabet point-to-point joint source-channel codes.

[A1]

Every word sk∈{0,1}k has source probability 2−k>0.

[A2]

In this verification, H(PS):=−∑sPS(s)ln⁡PS(s) and h(q):=−qln⁡q−(1−q)ln⁡(1−q), with 0ln⁡0:=0.

[F1]

Finite discrete memoryless channels: for the BSC with crossover probability 1/4, each coordinate transition probability is either 1/4 or 3/4, so every output word has positive probability under every input word.

[F2]

Single-letter information capacity of a finite DMC and Operational capacity formula for a finite DMC: C(W)=max⁡PXI(X;Y) in nats per use.

[F5]

Lossless separation for finite IID sources and finite DMCs: a strict entropy-capacity gap ensures reliable transmission by a sequence of codes, asymptotically.

Counterexample

1.1A1A2F2F3F4givenalgebra

The source entropy is H(PS)=ln⁡2. For a BSC with crossover 1/4 and input X∼Bern⁡(r), the output parameter is q=1/4+r/2, and [F3] gives I(X;Y)=h(q)−h(1/4). By [F4], the maximum is at r=1/2, so C(W)=ln⁡2−h(1/4)=34ln⁡3−ln⁡2.

1.2A1F1givenchoosealgebra

Fix any k≥1, any deterministic encoder fk:{0,1}k→{0,1}6k, and decoder gk:{0,1}6k→{0,1}k. Choose any output word y0 and then a source word sk≠gk(y0), which exists because ∣{0,1}k∣≥2. By [A1] and [F1], Pr⁡[Sk=sk,Y6k=y0]=2−kW6k(y0∣fk(sk))>0. On this event the decoder is wrong, so the block-error probability is positive for every finite code.

2.1A1A2F5step 1.1algebra

Hence 6C(W)−H(PS)=92ln⁡3−7ln⁡2>0, since 39=19683>16384=214. The asymptotic threshold is strict, so [F5] gives a reliable code sequence at ratio six.

3.1F5step 2.1step 1.2algebra∎

The strict asymptotic threshold in step 2.1 therefore cannot imply a zero-error code at each finite blocklength ratio. This refutes the statement while leaving the asymptotic separation conclusion intact.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

33 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources