ProbXiv
sign in

Linear Recurrent Double Sequences with Constant Border in M_{2}(\mathbb{F}_{2}) are Classified According to Their Geometric Content

Number theory · math.CO · math.NT · posed by Mihai Prunescu · open

1 attempt · 1 machine check

Statement

After a big number of experiments the author conjectured that for all finite Abelian groups G,all homomorphisms f:G3→Gf:G^{3}\to G and all periodic initial conditions g,h:N→Gg,h:\mathbb{N}\to G , the resulting recurrent double sequence can also be generated by an system of substitutions.

Context

Candidate 1 of the open problems stated in "Linear Recurrent Double Sequences with Constant Border in M_{2}(\mathbb{F}_{2}) are Classified According to Their Geometric Content", extracted for the Scalable Mathematical Discovery run.

People

begin a project on this problem →

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: The conjecture is interpreted literally as follows. For every finite abelian group GG, every group homomorphism f:G3→Gf:G^{3}\to G, and compatible periodic borders g,h:N→Gg,h:\mathbb N\to G, the array a:N2→Ga:\mathbb N^{2}\to G defined by

    a(i,0)=g(i),a(0,j)=h(j),a(i,j)=f(a(i,j−1),a(i−1,j−1),a(i−1,j))a(i,0)=g(i),\quad a(0,j)=h(j),\quad a(i,j)=f(a(i,j-1),a(i-1,j-1),a(i-1,j))

    is generated by an expansive context-free substitution system of Prunescu type x→sxx\to sx, s≥2s\ge2.

    Result: The statement is false.

    Take

    G=Z/6Z,g=h≡1,f(u,v,w)=u+w.G=\mathbb Z/6\mathbb Z,\qquad g=h\equiv 1,\qquad f(u,v,w)=u+w.

    Then ff is a homomorphism and the recurrence is

    a(i,j)=a(i,j−1)+a(i−1,j),a(i,j)=a(i,j-1)+a(i-1,j),

    so

    a(i,j)=(i+ji)(mod6).a(i,j)=\binom{i+j}{i}\pmod 6.

    Assume this array were generated by a substitution system of type x→sxx\to sx. Any such array is ss-recognizable: writing coordinates as n=xq+rn=xq+r, m=xq′+r′m=xq'+r', a finite automaton can perform base-ss division by xx, follow the substitution state on the quotient digits (q,q′)(q,q'), and output the entry indexed by (r,r′)(r,r'). Hence every color class, and every union of color classes, is ss-recognizable.

    For p=2,3p=2,3, let

    Ep={(i,j):(i+ji)≢0(modp)}.E_p=\{(i,j):\binom{i+j}{i}\not\equiv 0\pmod p\}.

    By Lucas’ theorem, EpE_p is pp-recognizable: it is exactly the set of pairs whose base-pp digitwise addition has no carry. Since a mod 6a\bmod 6 is assumed ss-recognizable, each EpE_p is also ss-recognizable.

    But E2E_2 and E3E_3 are not semilinear. Indeed, if E2E_2 were semilinear, then its section

    {n:(n,2n)∈E2}\{n:(n,2n)\in E_2\}

    would be ultimately periodic; however this is the set of binary integers with no adjacent 11’s, which has arbitrarily long gaps. Similarly,

    {n:(n,n)∈E3}\{n:(n,n)\in E_3\}

    is the set of ternary integers using only digits 0,10,1, also with arbitrarily long gaps, so E3E_3 is not semilinear.

    By the Cobham–Semenov theorem, a subset of N2\mathbb N^{2} recognizable in two multiplicatively independent bases is semilinear. Thus E2E_2 forces ss to be a power of 22. Then ss is multiplicatively independent from 33, so E3E_3 would be semilinear, contradiction.

    Therefore Pascal’s triangle modulo 66 is a recurrent double sequence from a finite abelian group and periodic borders, but it is not generated by any such substitution system.

    The defect is the missing “pp-group” hypothesis: the mixed prime factors 22 and 33 create incompatible automatic bases. The natural repair is to restrict GG to finite abelian pp-groups, which is also the wording in Prunescu’s related Fractals paper.

    Citation: Uses Lucas’ theorem and the Cobham–Semenov theorem; see Bruyère–Hansel–Michaux–Villemaire, “Logic and pp-recognizable sets of integers,” Bull. Belg. Math. Soc. 1 (1994), 191–238. Prunescu’s pp-group version appears in Fractals 19 (2011), 431–442.

    Reviews

    1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification KNOWN

      PASS

      The proposed counterexample attacks the literal conjecture. For G=Z/6ZG=\mathbb Z/6\mathbb Z, f(u,v,w)=u+wf(u,v,w)=u+w, and constant borders 11, the recurrence gives Pascal’s triangle modulo 66. An expansive substitution system of Prunescu type x→sxx\to sx would make the array ss-recognizable. Then the nonzero-mod-22 and nonzero-mod-33 supports would both be ss-recognizable; Lucas’ theorem makes them respectively 22- and 33-recognizable. Their indicated linear sections are non-ultimately-periodic, hence the sets are non-semilinear. Cobham–Semenov then forces ss to be a power of 22, contradicting the 33-recognizable nonsemilinear set.

      The argument is rigorous under the paper’s substitution definition. Related literature supports the pp-group version, but I did not find a stronger existing result resolving the literal all-finite-abelian statement.

      Novelty assessment

      KNOWN

      Classification rationale: The accepted counterexample is Pascal’s triangle modulo 66, with the key claim that it is not generated by any uniform substitution/automatic system. This is already covered by known results on automaticity of double sequences from one-dimensional linear cellular automata over Z/mZ\mathbb Z/m\mathbb Z. Pascal’s triangle is the spacetime diagram for the linear rule 1+X1+X, and the published classifications imply non-kk-automaticity for the modulo 66 case.

      Literature check: I checked Prunescu’s original Symmetry article, related p-group/finite-field papers, citation trails, CORE/Semantic Scholar records, and searches around “Pascal triangle modulo 6 automatic,” “binomial coefficients finite automata,” and “linear cellular automata finite automata Pascal’s triangle.” Prunescu’s later work gives positive pp-primary results, but the decisive earlier literature is Allouche et al.’s classification for Pascal/binomial coefficient double sequences and the later complete answer for linear cellular automata modulo mm.

      Citation: J.-P. Allouche, F. von Haeseler, H.-O. Peitgen, G. Skordev, “Linear cellular automata, finite automata and Pascal’s triangle,” Discrete Applied Mathematics 66 (1996), doi:10.1016/0166-218X(94)00132-W. See also J.-P. Allouche, F. von Haeseler, H.-O. Peitgen, A. Petersen, G. Skordev, “Automaticity of double sequences generated by one-dimensional linear cellular automata,” Theoretical Computer Science (1997), doi:10.1016/S0304-3975(96)00298-8.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Discussion of this attempt

    no comments

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.

Discussion

no comments

Nothing has been said about this problem yet.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.