With contributions from yarchik (DPDE formulation, PDE derivation) and E. Chan-López (Rule 22 symmetric analysis, symmetry classification)
ABSTRACT (original article): This paper is a direct continuation of Rule 30 Exact Binomial–Lucas Lifting (Part I). Where Part I established the algebraic pipeline from Boolean logic to support-set algebra, the present work reformulates the lifted integer recurrence as a Discrete Partial Difference Equation (DPDE) via generating polynomials (x). A -substitution reveals a hidden multiplicative factorization, and the polynomial degrees are proven to follow a Fibonacci sequence via an elegant shift argument. Taking the continuous limit of the DPDE yields a quasilinear first-order PDE whose characteristics encode the asymptotic growth of the integer coefficients. We solve this PDE analytically by the method of characteristics, obtaining explicit blow-up profiles. We then develop complete parallel decompositions for Rule 135 and Rule 22, revealing a fundamental symmetry classification: symmetric rules (Rule 22) produce parabolic reaction–diffusion equations with closed-form support cardinalities, while asymmetric rules (Rules 30 and 135) produce hyperbolic transport equations with divergent characteristics. The cumulative deviation between symmetric and asymmetric cases grows superlinearly, quantifying the algebraic cost of symmetry breaking. This framework suggests that the computational irreducibility of Rule 30 may be fundamentally rooted not in nonlinearity, but in the broken permutation symmetry of its local rule. CITATION (original author): Tigran Nersissian (2026), Rule 30 Exact Binomial–Lucas Lifting: From Boolean Logic to Integer Coefficients, Stirling Transfer, and Support-Set Algebra, arXiv:submit/7289701. Paper attached below.
P
m
Q
1. Introduction and Summary of Prior Results
1. Introduction and Summary of Prior Results
In Part I, we established a rigorous algebraic pipeline for Wolfram’s Rule 30 cellular automaton. Starting from a coordinate rotation that converts the two-sided update into a one-sided recursion b(m, n), we lifted the Boolean dynamics from to via prefix sums, expanded the resulting integer polynomials in the binomial basis , and proved that discrete integration reduces to pure index shifts. Reducing modulo 2 via Lucas’ Theorem yielded exact support sets governed by an OR-convolution recurrence, which we compressed into masked dyadic blocks for (log n) evaluation.
2
n |
r |
S
m
The present paper takes a fundamentally different perspective on the same algebraic objects. Rather than compressing the support sets into dyadic blocks, we reformulate the entire lifted recurrence as a Discrete Partial Difference Equation (DPDE) in the generating polynomials (x). This reformulation, discovered by yarchik, opens a powerful new avenue: the DPDE admits a well-defined continuous limit, yielding a quasilinear PDE whose analytic solution via the method of characteristics reveals the asymptotic structure of the integer coefficients.
P
m
Furthermore, we extend the algebraic pipeline to two companion cellular automata—Rule 135 and Rule 22—revealing a striking symmetry classification of the continuous limits. The three rules span the spectrum from full permutation symmetry (Rule 22, parabolic PDE) to partial asymmetry (Rule 135, hyperbolic with periodic blow-up) to maximal asymmetry (Rule 30, hyperbolic with monotone blow-up). This classification suggests that computational irreducibility is intimately linked to the symmetry structure of the local update rule.
2. The Discrete Partial Difference Equation
2. The Discrete Partial Difference Equation
The integer coefficients from Part I satisfy a complex trinomial convolution recurrence. The key insight of yarchik is that these coefficients are more naturally accessed through generating polynomials that encode the full binomial expansion of each row.
C
m,r
Definition 2.1 (Generating Polynomials). For each m ≥ 1, define the generating polynomial (x) by (x):=-1
,where are the integer coefficients from Part I and is the polynomial dimension.
P
m
P
m
k
m
∑
r=0
C
m,r
x |
r |
C
m,r
k
m
The initial conditions are (x)=1 and (x)=x. The connection to the automaton is: (n)=(n), the integer-lifted sequence from Part I.
P
1
P
2
P
m
a
m
Theorem 2.1 (The Discrete Partial Difference Equation (DPDE)). The generating polynomials satisfy the closed-form recurrence (x+1)-(x) = (x)+(x)+(x)·(x),with (x)=1 and (x)=x.The integer coefficients are recovered by the finite difference extraction formula: =
(j).
P
m
P
m
P
m-1
P
m-2
P
m-1
P
m-2
P
1
P
2
C
m,r
r
∑
j=0
r-j
(-1)
r |
j |
P
m
Proof. The left-hand side is the forward difference operator (x) = (x+1)-(x). From Part I, the lifted recurrence defines (n) = ((i)·(i)+(i)+(i)). Taking the forward difference in n removes the prefix sum, yielding (n) = (n)·(n)+(n)+(n). Identifying (x)=(x) gives the stated DPDE. The extraction formula is the standard binomial inversion: the forward difference operator applied r times at 0 recovers the r-th binomial coefficient. ◼
Δ
x
P
m
P
m
P
m
a
m
n-1
∑
i=0
a
m-1
a
m-2
a
m-1
a
m-2
Δ
n
a
m
a
m-1
a
m-2
a
m-1
a
m-2
P
m
a
m
Remark (A stunningly simple encoding). The DPDE compresses the entire trinomial convolution recurrence from Part I into a single line. All the complexity of the binomial product linearization, index-shifted summations, and constraint bounds is absorbed by the polynomial multiplication · and the forward difference operator.
P
m-1
P
m-2
Computational Verification
Computational Verification
The following Mathematica code verifies the DPDE and extracts the integer coefficients:
In[]:=
ClearAll[P,CSeq,GetRow];P[1,x_]=1;P[2,x_]=x;P[m_Integer,x_]:=P[m,x]=Expand[Sum[P[m-1,t]+P[m-2,t]+P[m-1,t]*P[m-2,t],{t,0,x-1}]];(*ExtractC_{m,r}viafinitedifferenceformula*)CSeq[m_Integer,r_Integer]:=Sum[(-1)^(r-j)*Binomial[r,j]*P[m,j],{j,0,r}];(*Helpertoprintnon-zeroelementsofarow*)GetRow[m_Integer]:=Module[{r=Floor[m/2],vals={},val},While[(val=CSeq[m,r])>0,AppendTo[vals,C[m,r]->val];r++;];vals];(*Verification*)GetRow[3](*{C[3,1]->1,C[3,2]->2}*)GetRow[4](*{C[4,2]->3,C[4,3]->8,C[4,4]->6}*)GetRow[5](*{C[5,2]->1,C[5,3]->17,...}*)GetRow[6](*{C[6,3]->7,C[6,4]->356,...}*)
Out[]=
{C[3,1]1,C[3,2]2}
Out[]=
{C[4,2]3,C[4,3]8,C[4,4]6}
Out[]=
{C[5,2]1,C[5,3]17,C[5,4]125,C[5,5]362,C[5,6]430,C[5,7]180}
Out[]=
{C[6,3]7,C[6,4]356,C[6,5]9933,C[6,6]111392,C[6,7]605995,C[6,8]1802876,C[6,9]3095036,C[6,10]3061752,C[6,11]1621800,C[6,12]356400}
3. The Q-Substitution and Fibonacci Degree Proof
3. The Q-Substitution and Fibonacci Degree Proof
The right-hand side of the DPDE contains a hidden algebraic structure that is revealed by a simple shift.
3.1 The Hidden Factorization
3.1 The Hidden Factorization
Lemma 3.1 (Algebraic factorization of the DPDE source term). For any a, b, the expression a + b + ab factors as
a + b + ab = (1 + a)(1 + b) − 1.
a + b + ab = (1 + a)(1 + b) − 1.
Proof. Expand: (1 + a)(1 + b) = 1 + a + b + ab. Subtract 1. ◼
Definition 3.1 (Shifted polynomials). Define the shifted polynomial sequence
(x):=(x)+1.
Q
m
P
m
Theorem 3.1 (Factored DPDE). The shifted polynomials satisfy the multiplicatively factored recurrence
(x) = (x)·(x)-1,
with(x)=2 and (x)=x+1.
Δ
x
Q
m
Q
m-1
Q
m-2
with
Q
1
Q
2
Proof. Since = (shifting by a constant does not affect differences), apply Lemma 3.1:
++· = = ·-1.
The initial conditions follow from=+1=2 and =+1=x+1. ◼
Δ
x
Q
m
Δ
x
P
m
P
m-1
P
m-2
P
m-1
P
m-2
(+1)(+1)-1
P
m-1
P
m-2
Q
m-1
Q
m-2
The initial conditions follow from
Q
1
P
1
Q
2
P
2
Remark. This factored form reveals the multiplicative coupling between layers. The −1 term acts as a constant “detuning” that prevents the recurrence from being purely multiplicative.
3.2 Fibonacci Degree Growth via the Q-Shift
3.2 Fibonacci Degree Growth via the Q-Shift
In Part I, we established the Fibonacci degree growth =++1 by direct analysis. The Q-substitution provides an elegant proof via a second shift that absorbs the inhomogeneous +1.
d
m
d
m-1
d
m-2
Theorem 3.2 (Fibonacci degree growth). Let :=deg(). Define :=+1. Then
=+
with=1, =2. Therefore = and
=-1.
d
m
Q
m
D
m
d
m
D
m
D
m-1
D
m-2
with
D
1
D
2
D
m
F
m+1
d
m
F
m+1
Proof. From the factored DPDE, multiplying · yields a polynomial of degree +. Taking the discrete integral (solving the forward difference) increases the degree by exactly +1. Subtracting 1 does not affect the degree. Therefore:
=++1.
Substituting=-1 into the degree recurrence:
-1=(-1)+(-1)+1
which simplifies to=+. We verify the initial conditions:
=1 =2 =0 =1=.
=x =x+1 =1 =2=.
Since satisfies the Fibonacci recurrence with = and =, we conclude = for all m ≥ 1. ◼
Q
m-1
Q
m-2
d
m-1
d
m-2
d
m
d
m-1
d
m-2
Substituting
d
m
D
m
D
m
D
m-1
D
m-2
which simplifies to
D
m
D
m-1
D
m-2
P
1
Q
1
d
1
D
1
F
2
P
2
Q
2
d
2
D
2
F
3
Since
D
m
D
1
F
2
D
2
F
3
D
m
F
m+1
4. The Continuous PDE Limit for Rule 30
4. The Continuous PDE Limit for Rule 30
We now treat m and x as continuous variables, setting u(x, m) ≃ (x), and derive the leading-order PDE governing the asymptotic behavior of the generating polynomials.
P
m
4.1 Derivation via Taylor Expansion
4.1 Derivation via Taylor Expansion
Define v(x, m) = u(x, m) + 1, so that v ≃ (x). The factored DPDE becomes:
v(x,m) = v(x, m−1) · v(x, m−2) − 1.
Q
m
Δ
x
Step 1: Replace the left-hand side. The forward difference with step size 1 becomes, to leading order: v = v(x+1, m) − v(x, m) ≃ .
Δ
x
Δ
x
∂v
∂x
Step 2: Expand the right-hand side. Expand each factor around the point m:
v(x,m-1)≃v-+-⋯
v
m
1
2
v
mm
v(x,m-2)≃v-2+2-⋯
v
m
v
mm
Multiplying and keeping only terms up to first derivatives (the dominant balance):
v(x,m-1)·v(x,m-2)≃(v-)(v-2)=-3v+2
v
m
v
m
2
v
v
m
2
v
m
In the leading-order continuous limit, we drop the term (higher-order relative to when v is large), giving:
2
v
m
v
v
m
v(x,m-1)·v(x,m-2)≃-3v
2
v
v
m
Step 3: Assemble the PDE. Substituting into =-3v-1 and switching back to u = v − 1:
v
x
2
v
v
m
u
x
2
u
u
m
2
u
u
m
Theorem 4.1 (Continuous PDE Limit for Rule 30). The leading-order continuous limit of the Rule 30 DPDE is the quasilinear first-order PDE + 3(u + 1) = u(u + 2).This is a hyperbolic transport equation with state-dependent wave speed 3(u + 1) and source term u(u + 2).
∂u
∂x
∂u
∂m
Remark (On the approximation). The continuous limit drops the term and all higher-order Taylor corrections. This is justified in the regime where u (and hence v) is large compared to its derivatives—i.e. for the dominant coefficients deep in the bulk of the distribution. At the tails, the discrete structure matters and the PDE is only approximate.
2
2
v
m
5. Solving the PDE by Method of Characteristics
5. Solving the PDE by Method of Characteristics
For a quasilinear PDE of the form +f(u)=g(u), the method of characteristics converts it into a system of ODEs along curves (x(s), m(s)) in the (x, m) plane.
u
x
u
m
5.1 The Characteristic System
5.1 The Characteristic System
5.2 Solving for u(x) Along a Characteristic
5.2 Solving for u(x) Along a Characteristic
The first ODE is separable. Using partial fractions:
Integrating both sides:
Exponentiating and solving for u:
5.3 Solving for m(x) Along a Characteristic
5.3 Solving for m(x) Along a Characteristic
We need dm/dx = 3(u + 1). From the solution above:
5.4 The Implicit General Solution
5.4 The Implicit General Solution
The two constants of integration along characteristics are:
Remark (Physical interpretation). The first invariant labels each characteristic curve. The solution shows that u grows monotonically and blows up at a finite x, with the blow-up location depending on the initial data through A. Near the blow-up, the generating polynomial coefficients exhibit the super-exponential growth observed empirically in the tables of Part I.
6. Rule 135: A Companion Algebraic Decomposition
6. Rule 135: A Companion Algebraic Decomposition
The same algebraic framework developed for Rule 30 applies, with interesting structural simplifications, to Wolfram’s Rule 135. We record the complete parallel construction.
6.1 The Local Rule and Its ANF
6.1 The Local Rule and Its ANF
Compare Rule 30’s ANF: a ⊕ b ⊕ c ⊕ b·c. The linear terms in b and c are absent, replaced by a bare constant 1.
6.2 The Discrete Partial Difference Equation
6.2 The Discrete Partial Difference Equation
Lifting to the integers, the DPDE for Rule 135 is:
6.3 The Integer Coefficients
6.3 The Integer Coefficients
The maximum binomial index follows a modified Fibonacci bound:
The first few rows of integer coefficients for Rule 135:
6.4 The Set Recurrence (Modulo 2 Projection)
6.4 The Set Recurrence (Modulo 2 Projection)
6.5 The Continuous PDE Limit
6.5 The Continuous PDE Limit
The method of characteristics gives:
7. Rule 22: The Symmetric Reference Case
7. Rule 22: The Symmetric Reference Case
Rule 22 provides a fundamental counterpoint to Rules 30 and 135. Its ANF is fully symmetric under permutations of (a, b, c), and this symmetry profoundly constrains the algebraic structure of the support sets.
7.1 The Local Rule and Its ANF
7.1 The Local Rule and Its ANF
This ANF is fully symmetric under all permutations of (a, b, c). Compare:
• Rule 30: a ⊕ b ⊕ c ⊕ b·c (asymmetric: b and c are coupled but a is not)
• Rule 135: 1 ⊕ a ⊕ b·c (asymmetric: a is distinguished)
• Rule 22: a ⊕ b ⊕ c ⊕ a·b·c (fully symmetric)
• Rule 30: a ⊕ b ⊕ c ⊕ b·c (asymmetric: b and c are coupled but a is not)
• Rule 135: 1 ⊕ a ⊕ b·c (asymmetric: a is distinguished)
• Rule 22: a ⊕ b ⊕ c ⊕ a·b·c (fully symmetric)
7.2 Closed-Form Support Cardinality
7.2 Closed-Form Support Cardinality
The symmetry of Rule 22 enables a remarkable closed-form expression for the cardinality of the support sets.
Remark. This closed form is a consequence of the fractal self-similarity that the symmetric ANF imposes on the support-set recursion. The sets themselves exhibit a clean two-step recursive structure: a “thickening” step for odd layers and a “decimation” step for even layers.
7.3 The Continuous PDE Limit
7.3 The Continuous PDE Limit
The symmetric ANF of Rule 22 produces a fundamentally different continuous limit.
8. Symmetry Classification: Parabolic vs. Hyperbolic Limits
8. Symmetry Classification: Parabolic vs. Hyperbolic Limits
8.1 Comparative Table of PDE Limits
8.1 Comparative Table of PDE Limits
8.2 The Symmetry Thesis
8.2 The Symmetry Thesis
The comparison across the three rules suggests a fundamental principle:
Conjecture 8.1 (Symmetry controls PDE type and tractability). For elementary cellular automata whose nonlinearity derives from a k-ary product term in the ANF:
(i) If the ANF is fully symmetric under permutation of its arguments, the continuous limit is parabolic (reaction–diffusion), and the support-set cardinality admits a closed form.
(ii) If the ANF breaks permutation symmetry, the continuous limit is hyperbolic (transport), and the support-set algebra exhibits increasing structural complexity.
The degree of symmetry breaking controls both the type of continuous limit and the algebraic tractability of the support structures.
(i) If the ANF is fully symmetric under permutation of its arguments, the continuous limit is parabolic (reaction–diffusion), and the support-set cardinality admits a closed form.
(ii) If the ANF breaks permutation symmetry, the continuous limit is hyperbolic (transport), and the support-set algebra exhibits increasing structural complexity.
The degree of symmetry breaking controls both the type of continuous limit and the algebraic tractability of the support structures.
8.3 Quantifying the Deviation: Rule 22 vs. Rule 30
8.3 Quantifying the Deviation: Rule 22 vs. Rule 30
To make the symmetry thesis precise, we compare the support-set cardinalities of Rule 22 (symmetric baseline) and Rule 30 (asymmetric case). Define the deviation:
The following code computes this deviation:
The log-log fit:
8.4 Structural Interpretation
8.4 Structural Interpretation
The deviation ϵ(m) quantifies the cumulative effect of the symmetry-breaking transport term. While Rule 22’s diffusive limit preserves spatial correlations (allowing closed-form cardinality), Rule 30’s hyperbolic limit scrambles phase information via characteristic divergence.
In this sense, Rule 30 may be viewed as a perturbation of a more rigid symmetric structure, where the deviation ϵ(m) captures the cumulative algebraic cost of symmetry breaking.
9. Discussion and Open Problems
9. Discussion and Open Problems
This paper has established three principal results beyond the foundations of Part I:
◼
3. The symmetry classification. By extending the framework to Rules 135 and 22, we identify a fundamental dichotomy: symmetric rules produce parabolic (diffusive) continuous limits with closed-form support cardinalities, while asymmetric rules produce hyperbolic (transport) limits with structurally complex support algebras.
Several problems remain open:
◼
Open Problem 2 (Discrete-to-continuous bridge). Can the PDE characteristics be used to constrain the modulo 2 behavior of the coefficients? The continuous limit governs the dominant coefficients, but the support sets depend on the parity structure at all scales.
◼
Open Problem 3 (Formal symmetry classification). Extend the parabolic/hyperbolic classification to all 256 elementary cellular automata. Which rules admit parabolic limits? Is the classification stable under rule equivalence classes (complement, mirror, complement-mirror)?
The central message of both papers is that Rule 30’s complexity can be understood algebraically through a precise sequence of translations: from Boolean logic to integer calculus, from discrete recurrences to continuous PDEs, and from individual rules to symmetry classes. The irreducibility of the center column appears to be rooted not in the difficulty of any single translation, but in the accumulation of symmetry-breaking effects across the +1 carry collisions that the Inc operator induces at every layer.
10. Complete Mathematica Implementation
10. Complete Mathematica Implementation
We provide the full Mathematica code for all computations in this paper: the DPDE verification, Rule 135 support-set generation, and the symmetry comparison.
10.1 DPDE Generating Polynomials (Rule 30)
10.1 DPDE Generating Polynomials (Rule 30)
10.2 DPDE Generating Polynomials (Rule 135)
10.2 DPDE Generating Polynomials (Rule 135)
10.3 Support-Set Algebra (Rule 30)
10.3 Support-Set Algebra (Rule 30)
10.4 Support-Set Algebra (Rule 135)
10.4 Support-Set Algebra (Rule 135)
10.5 Rule 135 from support set
10.5 Rule 135 from support set
References
References
[1] Wolfram, S. (1983). Statistical mechanics of cellular automata. Reviews of Modern Physics, 55(3), 601–644.
[2] Wolfram, S. (1986). Random sequence generation by cellular automata. Advances in Applied Mathematics, 7(2), 123–169.
[3] Wolfram, S. (2002). A New Kind of Science. Wolfram Media.
[4] Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley.
[5] Lucas, É. (1878). Théorie des Fonctions Numériques Simplement Périodiques. American Journal of Mathematics, 1(2), 184–196.
[6] Nersissian, T. (2025). Rule 30 Exact Binomial–Lucas Lifting: From Boolean Logic to Integer Coefficients, Stirling Transfer, and Support-Set Algebra. Wolfram Community Staff Picks.
[9] Martin, O., Odlyzko, A. M., & Wolfram, S. (1984). Algebraic properties of cellular automata. Communications in Mathematical Physics, 93(2), 219–258.
[10] Rowland, E. S. (2006). Local nested structure in rule 30. Complex Systems, 16(3), 239–258.
[11] Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology — EUROCRYPT '93, Lecture Notes in Computer Science, vol. 765, pp. 386–397.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK