Sums of products of binomial coefficients mod 2 and run length transforms of sequences

Basic Information

• Paper ID: 1610.06166
• Title: Sums of products of binomial coefficients mod 2 and run length transforms of sequences
• Author: Chai Wah Wu (IBM Research AI, IBM T. J. Watson Research Center)
• Classification: math.CO (Combinatorics)
• Publication Date: Initial submission October 19, 2016; latest revision August 12, 2022
• Paper Link: https://arxiv.org/abs/1610.06166v10

Abstract

This paper investigates the functional properties of binomial coefficients modulo 2, deriving a collection of recurrence relations for sums of products of binomial coefficients modulo 2. The research demonstrates that the sequences generated by these recurrence relations are run length transforms of several well-known fundamental sequences. In particular, the paper obtains explicit formulas for the run length transforms of positive integers, Fibonacci numbers, extended Lucas numbers, and Narayana's cattle sequence.

Research Background and Motivation

Problem Background

1. Core Problem: Determine when binomial coefficients $\binom{n}{k}$ are even or odd, i.e., compute $\binom{n}{k} \mod 2$
2. Classical Results: Pascal's triangle modulo 2 exhibits a fractal structure corresponding to the Sierpiński gasket
3. Theoretical Foundation: Lucas' theorem provides a simple method for computing binomial coefficients modulo a prime. For p=2, $\binom{n}{k}$ is even if and only if there exists a bit position i where the binary representations satisfy $n_i < k_i$

Research Significance

1. Theoretical Importance: Connects combinatorics, number theory, and bitwise operations in computer science
2. Practical Value: Run length transforms are useful for analyzing the number of ON cells after n iterations of cellular automata
3. Unified Framework: Establishes deep connections between binomial coefficients modulo 2 and famous integer sequences

Limitations of Existing Methods

• Although Lucas' theorem provides a decision method, systematic research on recurrence relations for sums of products of binomial coefficients is lacking
• The connection between run length transforms and binomial coefficients modulo 2 has not been fully explored
• A unified framework for characterizing run length transforms of different integer sequences is absent

Research Motivation

To systematically study properties of binomial coefficients modulo 2 using bitwise operations, establish connections with run length transforms, and provide new perspectives for understanding cellular automata and integer sequences.

Core Contributions

1. Theoretical Framework: Introduces functions $F(n,k) = \binom{a_1n+a_2k}{a_3n+a_4k}\binom{n}{k} \mod 2$ and corresponding bitwise function $g(n,k)$, systematically investigating their properties
2. Recurrence Relations: Derives multiple recurrence relations satisfied by $F(n,k)$ (Theorems 5, 13, 16), covering second-order, third-order, and fourth-order cases
3. Run Length Transform Formulas: Obtains explicit expressions for run length transforms of the following famous sequences:
   • Fibonacci sequence (Theorem 6)
   • Positive integers (Theorem 10)
   • Extended Lucas numbers (Theorem 17)
   • Narayana's cattle sequence (Theorem 14)
   • Other sequences (truncated Fibonacci, 1 plus powers of 2, etc.)
4. Unified Characterization: Proves that these run length transforms can be expressed as $a(n) = \sum_{k=0}^n F(n,k)$
5. Complete Classification: Summarizes 10 sequences and their run length transform coefficients $(a_1, a_2, a_3, a_4)$ in Table 1

Methodology Details

Task Definition

Input: Integer sequence $\{S_n\}_{n\geq 0}$ satisfying specific recurrence relations Output: Explicit expression for its run length transform $\{T_n\}_{n\geq 0}$Constraint: Characterized through sums of products of binomial coefficients modulo 2

Core Concepts

1. Run Length Transform (Definition 1)

For sequence $\{S_n\}_{n\geq 0}$, its run length transform $\{T_n\}_{n\geq 0}$ is defined as:

• $T_0 = S_0 = 1$
• For $n > 0$, $T_n = \prod_{i\in R} S_i$, where $R$ is the set of run lengths of consecutive 1's in the binary representation of $n$

Example: $n = 463 = 111001111_2$ has two runs of lengths 3 and 4, so $T_{463} = S_3 \cdot S_4$

2. Bitwise Representation (Theorems 1-3)

Using bitwise operations $\wedge$ (AND), $\vee$ (OR), $\neg$ (NOT):

Theorem 1: $\binom{n}{k} \equiv 0 \mod 2 \Leftrightarrow k \wedge (\neg n) \neq 0$

Theorem 2: $\binom{n}{k}\binom{m}{r} \equiv 0 \mod 2 \Leftrightarrow (k \wedge (\neg n)) \vee (r \wedge (\neg m)) \neq 0$

Theorem 3: Generalization to products of multiple binomial coefficients

Model Architecture

Definition 2: Core Function Definition

For integers $a_1, a_2, a_3, a_4$ satisfying $0 \leq a_1 + a_2$ and $0 \leq a_3 + a_4$, define:

$F(n,k) = \binom{a_1n+a_2k}{a_3n+a_4k}\binom{n}{k} \mod 2$

$g(n,k) = ((a_3n+a_4k)\wedge\neg(a_1n+a_2k)) \vee (k\wedge\neg n)$

Key Property: $F(n,k) = 1 \Leftrightarrow g(n,k) = 0$

Theorem 5: Second-Order Recurrence Relations

$F(n,k)$ satisfies the following properties:

• $F(n,k) = 0$ if $k > n$
• $F(2^rn, 2^rk) = F(n,k)$ (scaling invariance)
• $F(2n, 2k+1) = 0$ and other vanishing properties
• Under specific conditions: $F(4n+1, 4k) = F(n,k)$
• Condition determination based on $a_3 \wedge \neg a_1 \mod 4$

Lemma 2: Sequence Recurrence

The sequence $a(n) = \sum_{k=0}^n F(n,k)$ satisfies:

• $a(0) = 1$
• $a(2^rn) = a(n)$
• Under appropriate conditions: $a(4n+1) = a(n) + \sum_{k=0}^n F(4n+1, 4k+1)$

Technical Innovations

1. Bitwise Perspective: Transforms Lucas' theorem into bitwise operations, making recurrence relation derivations more intuitive and systematic
2. Unified Framework: Through different values of parameters $(a_1, a_2, a_3, a_4)$, uniformly characterizes run length transforms of multiple famous sequences
3. Modular Arithmetic Techniques: Uses $ia_3 \wedge \neg ia_1 \mod 2^m$ to determine vanishing properties of $F$, which is key to deriving recurrence relations
4. Recurrence Hierarchy: Generalizes from second-order (Theorem 4) to third-order (Theorem 12) and fourth-order (Theorem 12), demonstrating method extensibility
5. Explicit Construction: Not only proves existence but provides concrete coefficient choices, making results computable and verifiable

Experimental Setup

Verification Method

This is a pure mathematical theory paper employing theorem proving rather than experimental verification:

1. Proof Strategy:
   • Rigorous derivation through algebraic properties of bitwise operations
   • Analysis using least significant bits of binary representations
   • Verification of recurrence relations by induction
2. Concrete Example Verification:
   • Provides numerical examples for each theorem
   • Example: run decomposition of $n=463=111001111_2$
3. OEIS Database Cross-Reference:
   • All resulting sequences have corresponding entries in OEIS (Online Encyclopedia of Integer Sequences)
   • Provides sequence numbers for independent verification

Dataset

Uses standard integer sequences from the OEIS database:

• A000045 (Fibonacci)
• A000027 (Positive integers)
• A000930 (Narayana's cattle sequence)
• A000032 (Lucas numbers)
• And 10 sequences total (see Table 1)

Experimental Results

Main Results

1. Run Length Transform of Fibonacci Numbers (Theorem 6)

Coefficients: $(a_1, a_2, a_3, a_4) = (1, -1, 0, 2)$

$a(n) = \sum_{k=0}^n \binom{n-k}{2k}\binom{n}{k} \mod 2$

Recurrence Relations:

• $a(0) = 1$
• $a(2n) = a(n)$
• $a(4n+1) = a(n)$
• $a(4n+3) = a(2n+1) + a(n)$

This is precisely the run length transform of the Fibonacci sequence $\{1,1,2,3,5,8,13,\ldots\}$ (OEIS A246028)

2. Run Length Transform of Positive Integers (Theorem 10)

Coefficients: $(a_1, a_2, a_3, a_4) = (1, 1, 1, -1)$

$a(n) = \sum_{k=0}^n \binom{n+k}{n-k}\binom{n}{k} \mod 2$

Recurrence Relations:

• $a(2n) = a(n)$
• $a(4n+1) = 2a(n)$
• $a(4n+3) = 2a(2n+1) - a(n)$

Corresponds to the run length transform of the positive integer sequence $\{1,2,3,4,5,\ldots\}$ (OEIS A106737)

3. Run Length Transform of Narayana's Cattle Sequence (Theorem 14)

Coefficients: $(a_1, a_2, a_3, a_4) = (1, -1, 0, 6)$

$a(n) = \sum_{k=0}^n \binom{n-k}{6k}\binom{n}{k} \mod 2$

Recurrence Relations (third-order):

• $a(8n+1) = a(8n+3) = a(n)$
• $a(8n+5) = a(2n+1)$
• $a(8n+7) = a(n) + a(4n+3)$

Corresponds to sequence $\{1,1,1,2,3,4,6,9,13,19,\ldots\}$ (OEIS A000930)

4. Run Length Transform of Extended Lucas Numbers (Theorem 17)

Coefficients: $(a_1, a_2, a_3, a_4) = (1, 2, 2, -1)$

$a(n) = \sum_{k=0}^n \binom{n+2k}{2n-k}\binom{n}{k} \mod 2$

Recurrence Relations (fourth-order):

• $a(16n+1) = a(16n+3) = a(16n+5) = a(16n+7) = a(n)$
• $a(16n+9) = a(16n+11) = 2a(2n+1)$
• $a(16n+13) = a(4n+3)$
• $a(16n+15) = a(8n+7) + a(4n+3)$

Corresponds to sequence $\{1,1,2,1,3,4,7,11,18,\ldots\}$ (OEIS A329723)

Complete Results Summary (Table 1)

Special Results

Theorem 11: Fixed Point Property of All-Ones Sequence $\sum_{k=0}^n \binom{n-k}{k}\binom{n}{k} \mod 2 = 1, \quad \forall n \geq 0$

That is, $(n-k,k)\binom{n}{k}$ is odd if and only if $k=0$. This can be explained geometrically through the Sierpiński triangle: moving right $k$ steps from the left edge to reach a point on the triangle, then moving diagonally $k$ steps further necessarily reaches a blank space.

Related Work

Theoretical Foundations

1. Lucas' Theorem (1878): Classical result for computing binomial coefficients modulo a prime
2. Fine (1947), Granville (1997): Arithmetic properties of binomial coefficients modulo prime powers
3. Stewart (1995), Weisstein: Connection between Pascal's triangle modulo 2 and the Sierpiński triangle

Run Length Transforms

4. Sloane (2018): Introduces run length transform concept in cellular automata analysis
   • Theorem 4: Recurrence relations satisfied by run length transforms of second-order recursive sequences
   • This paper generalizes to third-order (Corollary 1) and fourth-order (Corollary 2)

Related Sequence Research

5. Gould's sequence/Dress' sequence: $\sum_{k=0}^n \binom{n}{k} \mod 2$ is the run length transform of powers of 2 (OEIS A001316)
6. Leroy, Rigo, Stipulanti (2016): Generalized Pascal triangles for binomial coefficients of words
7. Mathonet et al. (2022): Numerical sequences related to Pascal's triangle

Advantages of This Work

• Systematicity: Provides unified framework rather than case-by-case studies
• Explicitness: Gives concrete binomial coefficient sum expressions
• Extensibility: Methods generalize to higher-order recurrences
• Completeness: Covers multiple families of famous sequences

Conclusions and Discussion

Main Conclusions

1. Theoretical Contribution: Establishes profound connections between binomial coefficients modulo 2 and run length transforms; different integer sequences can be characterized through parameter choices $(a_1,a_2,a_3,a_4)$
2. Methodological Innovation: Bitwise perspective provides effective tools for systematically deriving recurrence relations, avoiding case-by-case analysis
3. Concrete Results: Obtains explicit formulas for run length transforms of 10 famous sequences including Fibonacci, Lucas, and Narayana's cattle sequence
4. Unified Framework: Proves that these run length transforms can all be expressed as $\sum_{k=0}^n \binom{a_1n+a_2k}{a_3n+a_4k}\binom{n}{k} \mod 2$

Limitations

1. Parameter Selection: While 10 examples are provided, systematic methods for determining coefficients $(a_1,a_2,a_3,a_4)$ for given sequences are lacking
2. Coverage Range: Only considers second-order, third-order, and fourth-order recurrences; higher-order cases have general theorems (Theorem 12) but lack concrete examples
3. Necessary and Sufficient Conditions: Does not fully characterize which sequences' run length transforms can be expressed in this form
4. Computational Complexity: Computing $a(n)$ for large $n$ requires summing $O(n)$ terms; more efficient algorithms may exist
5. Extension Directions:
   • Can this generalize to modulo other primes?
   • What about products of more than 2 binomial coefficients?

Future Directions

1. Inverse Problem: Given sequence $\{S_n\}$, how to systematically find coefficients $(a_1,a_2,a_3,a_4)$ such that its run length transform can be expressed as a binomial coefficient sum?
2. Algorithm Optimization: Develop more efficient algorithms to compute $a(n)$ directly without explicit summation
3. Generalization to $\mod p^k$: Study analogous properties of binomial coefficients modulo prime powers
4. Cellular Automata Applications: Use these results to analyze more cellular automaton rules
5. Combinatorial Interpretations: Seek combinatorial proofs (bijective proofs) of these identities

In-Depth Evaluation

Strengths

1. Theoretical Depth:
   • Cleverly transforms Lucas' theorem into bitwise language, making derivations more transparent
   • Recurrence relation derivations are rigorous and complete, with detailed proofs for each theorem
   • Unified framework possesses strong theoretical elegance
2. Methodological Innovation:
   • Bitwise perspective is a natural tool for modulo 2 problems, but underutilized in combinatorics; this paper demonstrates its power
   • Transforms binomial coefficient modulo 2 problems into pure bitwise operations through function $g(n,k)$
3. Rich Results:
   • Covers 10 famous sequences, each verified against OEIS
   • Complete treatment from second-order to fourth-order recurrences
   • Special results like Theorem 11 (all-ones sequence fixed point) provide valuable insights
4. Clear Exposition:
   • Precise definitions and consistent notation
   • Appropriate examples (e.g., run decomposition of $n=463$)
   • Table 1 provides clear result summary
5. Verifiability:
   • All sequences have OEIS numbers for independent verification
   • Recurrence relations can be verified computationally

Weaknesses

1. Lack of Algorithm Analysis:
   • No discussion of computational complexity
   • No pseudocode for efficient implementation
   • Practical utility for large-scale computation unclear
2. Inverse Problem Unresolved:
   • How to find coefficients $(a_1,a_2,a_3,a_4)$ for given sequences?
   • Can all run length transforms be expressed in this form?
   • Necessary conditions not fully characterized
3. Missing Combinatorial Interpretations:
   • While algebraic derivations are rigorous, combinatorial intuition is lacking
   • Why do these specific coefficients correspond to these sequences? Is there deeper reason?
4. Limited Application Scope:
   • Primarily theoretical results; cellular automata applications insufficiently discussed
   • Connections with other mathematical fields (number theory, algebra) not fully explored
5. Incomplete Higher-Order Cases:
   • Theorem 12 provides general framework, but fifth-order and higher lack concrete examples
   • Relationship between recurrence order and coefficient selection not discussed

Impact

1. Academic Value:
   • Provides new tools for intersection of combinatorics and number theory
   • May inspire research on other modulo-prime problems
   • Contributes multiple new sequences to OEIS (A329720, A329722, A329723)
2. Theoretical Significance:
   • Deepens understanding of Pascal's triangle modulo 2 structure
   • Bridges discrete sequences and bitwise operations
   • Provides rich examples for run length transform theory
3. Practical Value:
   • Applicable to cellular automata analysis
   • Potential applications in coding theory and cryptography (universality of modulo 2 operations)
   • Provides new sequence generation methods
4. Reproducibility:
   • All results verifiable through OEIS
   • Detailed proofs allow independent verification
   • Suitable as teaching material

Applicable Scenarios

1. Theoretical Research:
   • Identity proofs in combinatorics
   • Integer sequence property research
   • Modular arithmetic theory
2. Computer Science:
   • Cellular automata analysis
   • Bitwise operation optimization
   • Sequence generation algorithms
3. Mathematical Education:
   • Demonstrating bitwise operations in pure mathematics
   • Advanced applications of Lucas' theorem
   • Systematic study of recurrence relations
4. Related Fields:
   • Coding theory (binary codes)
   • Cryptography (modulo 2 operations)
   • Algorithm design (divide-and-conquer and binary representation)

References

Key references cited in the paper include:

1. Lucas' Theorem Foundations:
   • Fine (1947): "Binomial coefficients modulo a prime"
   • Granville (1997): "Arithmetic properties of binomial coefficients"
2. Sierpiński Triangle:
   • Stewart (1995): "Four encounters with Sierpiński's gasket"
   • Weisstein: MathWorld resources on Sierpiński sieve
3. Run Length Transforms:
   • Sloane (2018): "On the number of ON cells in cellular automata" (Cambridge University Press)
4. Computer Arithmetic:
   • Brent & Zimmermann (2010): "Modern Computer Arithmetic"
5. OEIS Database:
   • The On-Line Encyclopedia of Integer Sequences (1996-present)

Overall Assessment: This is a high-quality theoretical paper in combinatorics that systematically investigates the relationship between binomial coefficients modulo 2 and run length transforms through clever application of bitwise operations. The paper is theoretically rigorous, results are abundant, and exposition is clear, providing valuable tools and insights for related fields. Main limitations are the unresolved inverse problem and limited exploration of broader applications, but as a pure theoretical contribution, it is quite complete and profound.