{"id":"38c1f2ce-2ba2-4032-b289-579bc304fa8d","arxiv_id":"1908.02860","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Using a precomputed Pascal's triangle table, the OFDM-IM index selector runs in O(N) time with Θ(N²) space instead of O(N²) time or exponential LUT space.","lead":"The paper proposes a mapper for OFDM with Index Modulation that uses Pascal's triangle look-up tables to keep both time and space complexity polynomial while enabling all index modulation waveforms. This would remove a widely assumed computational barrier to the highest spectral-efficiency form of OFDM-IM.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed 'ideal setup' k=N/2 is not the argmax of the paper's own SE-gain formula; the PT mapper itself works for any k, but the 'maximal spectral efficiency' claim needs correction.","rationale":"The core algorithmic contribution is sound: a Pascal-triangle table of Theta(N^2) binomial entries lets the combinatorial-number-system index selector query each needed coefficient in O(1), and the total number of while-loop decrements telescopes to at most N-k, so the mapper runs in O(N) time for any k. The numerical experiments and the small parameter count support this. The reader's weakest assumption identifies the true soft spot: the paper asserts, via [4], that k=N/2 maximizes the SE gain over OFDM, but a direct calculation of the standard gain expression shows the asymptotic maximizer is k approximately 2N/3. This does not break the mapper, since the same construction works for any k, but it undermines the 'maximal spectral efficiency' framing of the title, abstract, and Lemmas 1-4. The reader's CONDITIONAL verdict remains appropriate: the paper should either correct the ideal-setup claim to the actual SE-maximizing k (with the mapper restated accordingly) or clarify that it is optimizing the number of index-modulation waveforms rather than SE gain over OFDM.","tokens_in":7629,"tokens_out":11775,"duration_ms":129708,"concrete_test":"Compute g(k)=floor(log2 C(N,k)) - (N-k) for M=2 and N=1000 over all k=1,...,N-1 using big-integer binomial coefficients, and find its argmax. If argmax k is near 667 rather than 500, the paper's ideal-setup premise fails; the PT mapper should then be restated for k=667 and the same O(N) time and Theta(N^2) space bounds verified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's advertised central claim is that M=2 with k=N/2 is the setup maximizing OFDM-IM spectral-efficiency gain over OFDM (Section I, used in Lemmas 1-4). Under the paper's own bit counts, m = p1 + k log2 M bits versus N log2 M for OFDM, so for M=2 the gain is floor(log2 C(N,k)) - (N-k). For large N, this is approximately N[H(alpha) - (1-alpha)] with alpha=k/N, whose maximum over alpha satisfies H'(alpha)+1=0, i.e., alpha=2/3, not 1/2. The PT-assisted mapper itself is not invalidated: Table I can be built for any k, and the IxS while-loop budget telescopes to at most N-k iterations, so O(N) time and Theta(N^2) space also hold for k=2N/3. The defect is load-bearing only for the title/abstract assertion that this is the maximal-SE setup; unless reference [4] is maximizing a different objective, the 'maximal spectral efficiency' framing is unsupported and should be corrected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the computational cost of the index selector (IxS) in OFDM with index modulation (OFDM-IM). The authors argue that under the setup M=2 and k=N/2 (called the ``ideal setup''), the original online IxS algorithm costs O(N^2) time, while a full 2^{p1}-entry lookup table would give O(N) time but Θ(2^N/√N) space. They propose replacing the online binomial-coefficient calculations with a Pascal-triangle table storing Θ(N^2) coefficients, and claim that this enables all 2^{p1} OFDM-IM waveforms in O(N) time with Θ(N^2) space. They also define a throughput scalability condition and show that the proposed mapper satisfies it.","tokens_in":7848,"tokens_out":7877,"duration_ms":89129,"significance":"The core algorithmic construction is clean, explicit, and parameter-free: if the missing loop-bound argument is supplied, the claimed O(N) time and Θ(N^2) space for the Pascal-triangle-assisted IxS is correct for any linear k, not just k=N/2. This is a valuable contribution because it removes the perceived need for subblock partitioning or exponential-size LUTs to enable all OFDM-IM waveforms, and it is independently verifiable from Algorithm 1 and Table I. However, the paper's identification of k=N/2 as the setup that maximizes the spectral-efficiency gain over OFDM is not derived and appears inconsistent with the paper's own bit-counting; this weakens the ``maximal spectral efficiency'' framing in the title and abstract, although it does not invalidate the mapper construction itself.","major_comments":[{"comment":"The claim that M=2 and k=N/2 is the setup that maximizes the OFDM-IM spectral-efficiency gain over OFDM is not established and appears to be incorrect under the paper's own bit counts. With M=2, the OFDM-IM mapper sends m=⌊log2 C(N,k)⌋+k bits while OFDM sends N bits, so the gain is ⌊log2 C(N,k)⌋-(N-k). For large N, this behaves as N[H(α)-(1-α)] - 0.5 log2 N + O(1) with α=k/N, whose continuous maximum is at α=2/3, not α=1/2. Thus k=N/2 maximizes p1 (Lemma 1's title is correct) but not the SE gain over OFDM. Since the title, abstract, Lemma 1's proof, and Theorem 2 rely on the ``maximal SE gain'' premise, the authors must either derive the claim from a clearly stated metric or correct the framing. The Pascal-triangle mapper itself works for any k, so the algorithmic results can be maintained after the correction.","section":"Section I and Lemma 1"},{"comment":"The proof that the table-assisted IxS runs in O(N) time is under-specified. Replacing each binomial-coefficient calculation by an O(1) table lookup changes the per-evaluation cost, but Lemma 4 does not bound the number of while-loop iterations in Algorithm 1. The sentence ``the inner loop ... reduces from O(k)×O(i) to O(k)×O(1)'' assumes one lookup per i, whereas the while loop may decrement ci several times. The conclusion is nevertheless correct: the candidate value starts at N-1 and strictly decreases on each decrement, so the total number of while-loop body executions across all i is at most N-1, giving O(N) evaluations once table lookups are O(1). This telescoping argument should be stated explicitly; it is load-bearing for Theorem 1. The same argument is also needed to justify the O(N^2) bound for the original algorithm in Section II-A, since the count k(k+1)/2 there appears to count only one binomial evaluation per i.","section":"Lemma 4 and Algorithm 1"}],"minor_comments":[{"comment":"The phrase ``computes O(N^2) distinct binomial coefficients'' is misleading: Algorithm 1 evaluates only O(N) coefficients per symbol, and the O(N^2) quantity is the number of entries in the Pascal-triangle table. Please rephrase to distinguish the table size from the number of queries.","section":"Lemma 4"},{"comment":"The table uses the convention C(n,i)=0 for n<i, as shown in the first rows. This convention should be stated explicitly in the text so that Algorithm 1's while loop termination is clear for small X.","section":"Table I"},{"comment":"The historical note on Pascal's triangle points to a Wikipedia URL; this is not appropriate for a published letter. Replace it with a standard reference on combinatorial number systems or Pascal's triangle.","section":"Footnote 2"},{"comment":"The sentence ``the throughput of the mapper is not scalable unless ineq. 1 does hold'' should read ``unless Inequality (1) holds''; the current wording is grammatically incomplete.","section":"Section II-D, Definition 1"}],"recommendation":"major_revision","confidential_remarks":"The ideal-setup problem is more than a local citation issue because it appears in the title and abstract. If reference [4] indeed maximizes a different objective, the authors should state that explicitly; otherwise the ``maximal spectral efficiency'' claim should be corrected to k=2N/3 for large N, which does not change the main algorithmic result. The missing while-loop bound in Lemma 4 is fixable and should be included in revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, the algorithmic contribution is real: replacing the binomial-coefficient recomputation in the OFDM-IM index selector with a Pascal-triangle lookup gives O(N) time and Θ(N²) space for any k, which directly handles the long-standing 'LUT is exponential' objection in the OFDM-IM literature. As far as I can tell, that specific application is new. Second, the paper's headline claim about 'maximal spectral efficiency' does not match the paper's own bit accounting.\n\nThe complexity analysis is basically sound. With O(1) table lookups, each while-loop step is cheap, and the total number of while-loop attempts is bounded because `largestCandidate` only decreases across the outer loop. So the O(N) time conclusion holds, and the comparison with the Θ(2^N/√N) LUT is a fair way to show the space saving. The numerical case study is simple but honest, and the throughput separation follows from the complexity gap. The citation to the authors' earlier work for the O(N²) baseline is appropriate, not circular.\n\nSoft spots, in order of severity. First, Lemma 4's proof is under-specified about the while-loop iteration count. It should explicitly argue that the total number of decrements is at most N-1+k, which makes the O(N) bound airtight. That is a minor fix, not a flaw in the result. Second, the premise that k=N/2 with M=2 maximizes the SE gain over OFDM is contestable. Using the paper's own bit counts, the gain for BPSK is floor(log2 C(N,k)) - (N-k). Stirling's approximation puts the large-N argmax near k=2N/3, not N/2. If reference [4] is maximizing a different objective (like the index-bit count p1 alone), the authors should say so explicitly. As written, the title and abstract rest on a premise the paper does not defend.\n\nWho this is for: people working on OFDM-IM or index-modulation complexity. They will appreciate the Pascal-triangle trick and will also want the framing fixed. I would send this to a serious referee. With a corrected SE claim or a clear definition of 'gain', it is a solid letter publication; without that correction, the headline overstates.\n\nRecommendation: engage with it, and ask the authors to tighten Lemma 4 and to either justify or drop the k=N/2 maximizing claim.","headline":"The Pascal-triangle mapper is a sound, useful result that deserves peer review; the 'maximal spectral efficiency' framing is contestable and should be corrected.","tokens_in":8365,"tokens_out":8572,"would_cite":true,"duration_ms":90759,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves all OFDM-IM waveforms can be mapped at OFDM speed using a Pascal-triangle table of quadratic size.","keywords":["OFDM with index modulation","index modulation","spectral efficiency","Pascal's triangle","computational complexity","index selector","look-up table","subblock partitioning"],"falsifier":"For $M=2$, evaluate $\\text{gain}_N(k)=\\lfloor\\log_2 C(N,k)\\rfloor-(N-k)$ over all $k$ for a large even $N$, say $N=1000$; if the maximizing $k$ is clearly not $N/2$, the 'ideal setup' premise behind the maximal-SE framing is wrong, and the comparison with OFDM would need to be re-based, even though the Pascal-triangle mapper's complexity results hold for every $k$.","tokens_in":7447,"feed_emoji":"📡","tokens_out":9381,"duration_ms":89712,"temperature":0.7,"pith_summary":"OFDM with Index Modulation (OFDM-IM) sends extra data by selecting which k of N subcarriers are active, and the index selector that makes that choice has been viewed as the scheme's computational bottleneck. The paper claims the bottleneck is removable: the binomial coefficients needed by the selector are exactly the entries of Pascal's triangle, so a precomputed table of $\\Theta(N^2)$ entries turns each $O(i)$ coefficient calculation into a single lookup. With that assist, the index selector runs in $O(N)$ time and the whole mapper runs at the same asymptotic speed as a plain OFDM mapper while enabling all $2^{p_1}$ waveforms. This would mean the maximal spectral-efficiency gain over OFDM can be obtained without subblock partitioning and without the exponential-size lookup table that the literature assumed was necessary.","feed_headline":"Pascal-triangle table unlocks full OFDM-IM at linear time","feed_subtitle":"Max spectral-efficiency gain no longer needs exponential storage; a quadratic Pascal table replaces the huge LUT.","key_machinery":"The load-bearing object is the Pascal-triangle table, an $N\\times(N/2)$ matrix whose entry in row $c$ and column $i$ is the binomial coefficient $C(c,i)$, the number of ways to choose $i$ items from $c$. The combinatorial number system behind the index selector guarantees that decoding a $p_1$-bit input reduces to a greedy sequence of comparisons between the input remainder and such coefficients, and the table answers each comparison in $O(1)$ instead of $O(i)$ multiplications. This is what collapses the index-selector complexity from $O(N^2)$ to $O(N)$ while keeping the selected active-subcarrier set identical to the original algorithm's.","core_discovery":"The paper's central claim, Theorem 1, is that all $2^{p_1}$ OFDM-IM waveforms can be mapped at the same asymptotic time as an OFDM mapper using polynomial space. Under the 'ideal setup' $M=2$ and $k=N/2$, $p_1=\\lfloor\\log_2 C(N,N/2)\\rfloor$ approaches $N-\\log_2\\sqrt{N}$, so a conventional LUT needs $\\Theta(2^N/\\sqrt{N})$ entries, while the Pascal-triangle table stores only $\\Theta(N^2)$ binomial coefficients. Replacing the $O(i)$ computation of each $C(c_i,i)$ in the greedy index selector with an $O(1)$ table lookup drops the index selector from $O(N^2)$ to $O(N)$ steps. The active-subcarrier sets produced are the same as the original mapper's, so the maximal spectral-efficiency gain is preserved while throughput scales rather than vanishing.","pith_inferences":["A direct comparison of the actual gain $\\lfloor\\log_2 C(N,k)\\rfloor-(N-k)$ for $M=2$ suggests the maximum may occur near $k=2N/3$ rather than $N/2$; if so, the paper's 'maximal SE' label is inherited from the cited reference rather than re-derived, although the mapper itself would still work at the true optimal $k$.","The combinatorial-number-system lookup trick is general: any index-modulation or spatial-modulation system that maps bits to a $k$-subset by greedy binomial search can reuse the same Pascal-triangle table, so the speedup likely transfers beyond OFDM.","Because $C(c,i)=C(c,c-i)$ and the table is triangular, a hardware implementation could exploit symmetry to store roughly half the entries, extending the practical $N$ range while preserving the asymptotic $\\Theta(N^2)$ bound.","The paper leaves open the question of whether the $\\Theta(N^2)$ storage can be reduced to $O(N)$; if such a reduction exists, OFDM-IM would match OFDM's asymptotic space as well as its time."],"forward_implications":["OFDM-IM can operate with all $N$ subcarriers in a single block, so subblock partitioning, which sacrifices spectral efficiency to reduce index-selector load, is no longer required.","The index selector ceases to be the most complex DSP block: mapper runtime is $O(N)$ and the throughput $m(N)/T(N)$ tends to a positive constant under the ideal setup.","The storage requirement drops from $\\Theta(2^N/\\sqrt{N})$ table entries to $\\Theta(N^2)$, making the full-waveform mapper practical at substantially larger $N$.","The Pascal-triangle acceleration works for any activation ratio $k$, not only $k=N/2$, because every coefficient $C(c_i,i)$ lies in the table."],"supporting_citations":[{"why":"Defines the OFDM-IM mapper and the index-selector algorithm whose per-coefficient $O(i)$ computation becomes the bottleneck.","marker":"[3]"},{"why":"Provides the premise that $M=2$ and $k=N/2$ give maximal spectral-efficiency gain over OFDM, the 'ideal setup' used throughout.","marker":"[4]"},{"why":"Earlier work that establishes the $O(N^2)$ complexity of the index selector and the throughput scalability metric used in the analysis.","marker":"[5]"},{"why":"Survey that frames the LUT-based index selector as practically infeasible for large $N$, the conjecture the paper overturns.","marker":"[2]"}],"fun_headline_variants":["Pascal's triangle tames full OFDM-IM mapping","All OFDM-IM waveforms at polynomial cost","Max SE for OFDM-IM with polynomial resources","Polynomial-time mapping for all OFDM-IM waveforms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument assumes, on the strength of a citation, that $M=2$ and $k=N/2$ is the configuration with the largest spectral-efficiency gain over OFDM, and the asymptotic claims are stated for that configuration.","fun_headline_variants_meta":{"raw":{"variants":["Pascal's triangle tames full OFDM-IM mapping","All OFDM-IM waveforms at polynomial cost","Max SE for OFDM-IM with polynomial resources","Polynomial-time mapping for all OFDM-IM waveforms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001255,"raw_usage":{"total_tokens":5119,"prompt_tokens":899,"completion_tokens":4220,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":515,"completion_tokens_details":{"reasoning_tokens":4155}},"tokens_in":515,"tokens_out":4220,"duration_ms":34035,"temperature":1.0,"reasoning_tokens":4155,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:32:59.486438+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $M=2$, evaluate $\\text{gain}_N(k)=\\lfloor\\log_2 C(N,k)\\rfloor-(N-k)$ over all $k$ for a large even $N$, say $N=1000$; if the maximizing $k$ is clearly not $N/2$, the 'ideal setup' premise behind the maximal-SE framing is wrong, and the comparison with OFDM would need to be re-based, even though the Pascal-triangle mapper's complexity results hold for every $k$.","supporting_citations":[{"cited_title":"Orthogonal frequency division multiplexing with index modulation,","cited_arxiv_id":null,"evidence_quote":"Defines the OFDM-IM mapper and the index-selector algorithm whose per-coefficient $O(i)$ computation becomes the bottleneck."},{"cited_title":"Generalization of orthogonal frequency division multiplexing with index modulation,","cited_arxiv_id":null,"evidence_quote":"Provides the premise that $M=2$ and $k=N/2$ give maximal spectral-efficiency gain over OFDM, the 'ideal setup' used throughout."},{"cited_title":"What is the cost of the index selector task for ofdm with index modulation?","cited_arxiv_id":null,"evidence_quote":"Earlier work that establishes the $O(N^2)$ complexity of the index selector and the throughput scalability metric used in the analysis."},{"cited_title":"Index modulation techniques for next-generation wireless networks,","cited_arxiv_id":null,"evidence_quote":"Survey that frames the LUT-based index selector as practically infeasible for large $N$, the conjecture the paper overturns."}],"review_version":1}