Pipeline-generated

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.

✓ 4 results · all verified · 0 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 4 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Relay and Interference Channel Bounds — Examples

1 · Prerequisites

2 · Summary

These examples test the cut-dependent relay calculation, the equality case of the finite strong-interference theorem, the failure of that formula outside its regime, and a numerical complex Gaussian strong-interference region. The Gaussian relay example uses the proved continuous-alphabet NNC construction on the A page with its stated fixed quantizer. The binary examples convert the finite suppliers’ nats convention explicitly to bits; the counterexample excludes the entire time-sharing union of the wrongly generalized formula.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck pendingOpen item page →

A two-hop Gaussian relay with a half-bit quantization penalty

Example

Consider a real three-node relay with unit power and unit noise variance at every node, source-to-relay gain $\sqrt{10}$ , relay-to-destination gain $\sqrt{10}$ , and zero direct gain. Use independent $X, X_{r} \sim N (0, 1)$ , a constant reconstruction at the source, the unquantized destination output, and the fixed relay quantizer ${\hat{Y}}_{r} = Y_{r} + {\hat{Z}}_{r}$ with independent ${\hat{Z}}_{r} \sim N (0, 1)$ . The noisy-network-coding rate for this fixed test channel is $R_{N N C} = \min {\frac{1}{2} \log_{2} 6, \frac{1}{2} \log_{2} 11 - \frac{1}{2}} = \frac{1}{2} \log_{2} 11 - \frac{1}{2} \approx 1.2297$ bits per use. The cut-set value is $\frac{1}{2} \log_{2} 11 \approx 1.7297$ , so this fixed quantizer's NNC rate is half a bit below that outer bound.

Facts & Assumptions

Given: The three-node Gaussian relay with the stated gains, power constraints, independent inputs, and fixed quantizer.

[A1]

Assume AC (The Axiom of Choice), as required by the Gaussian coding and entropy suppliers [F2] and [F3].

[F1]

Real scalar Gaussian multicast relay network and power constraints: the channel is memoryless additive Gaussian with per-node unit power and unit noise variance.

[F2]

Noise-level noisy-network-coding inner bound for real Gaussian multicast networks: for a cut $A$ and destination $d$ , NNC subtracts $I (Y_{A}; {\hat{Y}}_{A} ∣ X_{[N]}, Y_{d}, {\hat{Y}}_{A^{c}})$ from $I (X_{A}; Y_{d}, {\hat{Y}}_{A^{c}} ∣ X_{A^{c}})$ ; constant reconstructions are allowed.

[F3]

Gaussian maximizes differential entropy at fixed positive-definite covariance: Gaussian laws maximize differential entropy at fixed covariance, so the cut mutual informations are bounded by the corresponding Gaussian log expressions.

Proof

1.1A1F1givenalgebra

Assume [A1] and use the independent unit-variance Gaussian inputs and quantizer noise stated in the example. For the cut separating the source alone, the relay sees $\sqrt{10} X + Z_{r}$ , and adding independent unit-variance quantization noise makes total noise variance $2$ . Thus the NNC first-cut mutual information is $\frac{1}{2} \log_{2} (1 + 10 / 2) = \frac{1}{2} \log_{2} 6$ . The destination has no direct source term, so its observation adds zero information across this cut.

1.2F1F2givenalgebra

For the cut containing source and relay, the destination observes $\sqrt{10} X_{r} + Z_{d}$ , so $I (X, X_{r}; Y_{d}) = \frac{1}{2} \log_{2} (1 + 10) = \frac{1}{2} \log_{2} 11$ . Given all inputs and $Y_{d}$ , the relay observation noise and independent quantization noise have variances $1$ and $1$ , hence $I (Y_{r}; {\hat{Y}}_{r} ∣ X, X_{r}, Y_{d}) = \frac{1}{2} \log_{2} (2) = \frac{1}{2}$ . The two NNC cut rates are therefore the values in the minimum in the statement.

2.1F1F2F3step 1.1step 1.2algebra∎

The first cut is larger because $6 > 11 / 2$ (equivalently $12 > 11$ ), so the minimum is $\frac{1}{2} \log_{2} 11 - \frac{1}{2}$ . In the cut-set expression, the source cut is $I (X; Y_{r}, Y_{d} ∣ X_{r}) = I (X; Y_{r} ∣ X_{r}) \leq \frac{1}{2} \log_{2} 11$ and the relay-to-destination cut is $I (X, X_{r}; Y_{d}) = I (X_{r}; Y_{d}) \leq \frac{1}{2} \log_{2} 11$ , since the direct gain is zero; [F3] gives each Gaussian upper bound. Independent unit-power Gaussian inputs attain both terms, so the cut-set value is $\frac{1}{2} \log_{2} 11$ . Subtracting gives a gap of exactly $1 / 2$ bit.

Scope note

This is the rate of the stated fixed quantizer, not the optimized NNC rate. The general reconstruction-set coding statement [F2], with only the relay quantized, proves achievability of every strict rate below the displayed value and its closure.

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck pendingOpen item page →

The binary additive interference channel in the strong regime

Example

Let $X_{1} = X_{2} = Y_{1} = Y_{2} = {0, 1}$ and set $Y_{1} = X_{1} \oplus X_{2}, Y_{2} = X_{1} \oplus X_{2},$ where $\oplus$ is addition modulo two. The capacity region is $R_{1} \geq 0, R_{2} \geq 0, R_{1} \leq 1, R_{2} \leq 1, R_{1} + R_{2} \leq 1$ bits per use.

Facts & Assumptions

Given: All information quantities in this example are measured in bits: $I_{2} = I / \ln 2$ and $H_{2} = H / \ln 2$ for the nats-valued supplier conventions. Independent messages sent over the binary channel in the example.

[F1]

Finite two-user interference channel and strong-interference regime: strong interference requires the two conditional mutual-information inequalities for every product input law.

[F2]

Capacity region of a finite two-user interference channel under strong interference: under those universal inequalities, capacity is the intersection of the two multiple-access regions with time sharing.

Proof

1.1F1givenalgebra

For every product input law, conditioning on $X_{2}$ makes both $Y_{1}$ and $Y_{2}$ equal to $X_{1}$ plus the same fixed bit; hence $I_{2} (X_{1}; Y_{1} ∣ X_{2}) = I_{2} (X_{1}; Y_{2} ∣ X_{2})$ . Conditioning on $X_{1}$ gives $I_{2} (X_{2}; Y_{2} ∣ X_{1}) = I_{2} (X_{2}; Y_{1} ∣ X_{1})$ . Thus [F1] holds with equality.

1.2F2givenalgebra

Each receiver's output is one bit, so its multiple-access sum mutual information is at most $H_{2} (Y_{i}) \leq 1$ . Also, given the other input, each user sees a noiseless binary channel, whose mutual information is at most one bit. Therefore the region in [F2] is contained in the stated triangle.

2.1F1F2step 1.2algebra∎

With independent uniform inputs, $Y_{i}$ is uniform, and $I_{2} (X_{1}; Y_{1} ∣ X_{2}) = I_{2} (X_{2}; Y_{2} ∣ X_{1}) = I_{2} (X_{1}, X_{2}; Y_{i}) = 1$ . The MAC intersection contains the two corner points $(1, 0)$ and $(0, 1)$ ; the zero pair is achieved by singleton messages. Time sharing among these three points achieves every nonnegative pair with sum at most one. Together with step 1.2 this proves the capacity region.

CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck pendingOpen item page →

Outside the strong regime, the MAC intersection can be too small

Statement refuted

The MAC-intersection formula of Capacity region of a finite two-user interference channel under strong interference, if applied to every finite two-user interference channel without its strong-interference hypothesis, gives the exact capacity region.

Facts & Assumptions

[F1]

Finite two-user interference channel and strong-interference regime: the strong regime requires both mutual-information inequalities for every product input law.

[F2]

Capacity region of a finite two-user interference channel under strong interference: only under [F1] does the MAC-intersection formula give capacity.

Counterexample

1.1F1F2givenalgebra

Under independent uniform inputs, $I_{2} (X_{1}; Y_{1} ∣ X_{2}) = 1$ while $I_{2} (X_{1}; Y_{2} ∣ X_{2}) = 0$ . Thus the first strong-interference inequality fails, so the hypothesis of [F2] is absent.

1.2givenalgebra

Each receiver observes its own input noiselessly. A binary code of rate below one can therefore be sent independently by each user. Since each output alphabet has size two, no rate can exceed one bit per use. Taking closure gives the true capacity square.

2.1F2givenstep 1.2algebra∎

For every finite time-sharing variable $Q$ and every conditional product input law, each output is binary, so $I_{2} (X_{1}, X_{2}; Y_{i} ∣ Q) \leq H_{2} (Y_{i} ∣ Q) \leq 1$ . Consequently every rate pair in the entire union and its closure asserted by the formula in [F2] satisfies $R_{1} + R_{2} \leq 1$ bit per use. This excludes $(1, 1)$ , which step 1.2 places in the true capacity square. Hence the formula without the strong-interference hypothesis is false.

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck pendingOpen item page →

A numerical asymmetric Gaussian channel in the strong regime

Example

Use the complex Gaussian channel with $P_{1} = P_{2} = 1$ , unit noise variance, $h_{11} = 1$ , $h_{22} = 3 / 2$ , $h_{21} = 2$ , and $h_{12} = 5 / 2$ in the convention of Real and complex two-user Gaussian interference channels. Then ${S N R}_{1} = 1, {S N R}_{2} = \frac{9}{4}, {I N R}_{1} = 4, {I N R}_{2} = \frac{25}{4},$ and the exact capacity region is $R_{1} \geq 0, R_{2} \geq 0, R_{1} \leq 1, R_{2} \leq \log_{2} \frac{13}{4}, R_{1} + R_{2} \leq \log_{2} 6$ bits per use.

Facts & Assumptions

Given: The complex Gaussian interference channel and parameters in the example.

[A1]

Assume AC (The Axiom of Choice), as required by the Gaussian information and coding suppliers used in [F2].

[F1]

Real and complex two-user Gaussian interference channels: ${I N R}_{1} = ∣ h_{21} ∣^{2} P_{2}$ and ${I N R}_{2} = ∣ h_{12} ∣^{2} P_{1}$ ; complex scalar rates use $κ = 1$ .

[F2]

Exact strong-interference region for the two-user Gaussian interference channel: if $∣ h_{12} ∣ \geq ∣ h_{11} ∣$ and $∣ h_{21} ∣ \geq ∣ h_{22} ∣$ , capacity is the stated intersection of the two Gaussian MAC regions.

Proof

1.1A1F1F2givenalgebra

Assume [A1] and use the complex channel model [F1] with the stated unit power budgets and unit-variance noises. The gains satisfy $∣ h_{12} ∣ = 2.5 \geq 1 = ∣ h_{11} ∣$ and $∣ h_{21} ∣ = 2 \geq 1.5 = ∣ h_{22} ∣$ , so the strong-regime hypothesis of [F2] holds. The displayed SNR and INR values follow by squaring the gains and multiplying by unit powers.

2.1F1F2step 1.1algebra∎

The individual constraints in [F2] become $R_{1} \leq \log_{2} (2) = 1$ and $R_{2} \leq \log_{2} (1 + 9 / 4) = \log_{2} (13 / 4)$ . The two sum constraints are $\log_{2} (1 + 1 + 4) = \log_{2} 6$ and $\log_{2} (1 + 9 / 4 + 25 / 4) = \log_{2} (19 / 2)$ ; since $6 < 19 / 2$ , the first is active. This gives exactly the stated region.

Relay and Interference Channel Bounds — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

A two-hop Gaussian relay with a half-bit quantization penalty

Example

Facts & Assumptions

Proof

Scope note

The binary additive interference channel in the strong regime

Example

Facts & Assumptions

Proof

Outside the strong regime, the MAC intersection can be too small

Statement refuted

Facts & Assumptions

Counterexample

A numerical asymmetric Gaussian channel in the strong regime

Example

Facts & Assumptions

Proof

Sources