pith. sign in

arxiv: 2505.23974 · v4 · submitted 2025-05-28 · 🧮 math.CO · cs.IT· math.IT

Representation of Symmetric Shift Registers

Jan S{\o}reng This is my paper

Pith reviewed 2026-05-19 12:52 UTC · model grok-4.3

classification 🧮 math.CO cs.ITmath.IT
keywords shift registersnonlinear difference equationsperiodsarithmetic progressionsGF(2)sequences
0
0 comments X

The pith

Symmetric shift registers over GF(2) are represented as systems of nonlinear difference equations where arithmetic progressions determine the solutions and minimal periods.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out a framework that associates symmetric shift registers with systems of nonlinear difference equations defined over the field GF(2). Arithmetic progressions are positioned as the key device for describing the behavior of solutions to these equations. The representation is offered to make the internal organization of the registers more transparent and to simplify the task of calculating the shortest periods of the sequences they produce. A reader would care because period length is a basic property that governs how such registers can be used in generating long or repeating binary sequences.

Core claim

Symmetric shift registers admit a representation by associated systems of nonlinear difference equations over GF(2) in which arithmetical progressions play a central part; this representation clarifies the underlying structures and makes it easier to determine the minimal periods of the sequences generated by the registers.

What carries the argument

The representation of symmetric shift registers as systems of nonlinear difference equations over GF(2) whose solutions are governed by arithmetic progressions.

If this is right

  • The internal structures of symmetric shift registers become visible through the associated difference-equation systems.
  • Minimal periods of the generated sequences can be obtained directly from the arithmetic progressions in those systems.
  • The new representation supports systematic study of how the registers produce periodic binary sequences over GF(2).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the representation works, analogous difference-equation models might be constructed for other families of shift registers that lack the symmetry condition.
  • The same arithmetic-progression technique could be tested on sequences produced by registers of larger length to see whether the period formulas remain simple.

Load-bearing premise

Symmetric shift registers admit a faithful representation as systems of nonlinear difference equations over GF(2) whose solutions are governed by arithmetic progressions in a way that directly yields minimal periods.

What would settle it

A symmetric shift register whose generated sequence has a minimal period that cannot be read off from the arithmetic progression appearing in the associated system of nonlinear difference equations.

Figures

Figures reproduced from arXiv: 2505.23974 by Jan S{\o}reng.

Figure 1
Figure 1. Figure 1: The modified weight parameters of A ∞ 2 . In this figure we see three types of waves with different heights. These waves ”collide” and ”move” with different ”velocities”. But after the collisions they obtain there original form. These plots bear a resemblance to plots in soliton theory. We refer to [1]. We do not use these wave structures in the proofs. But there are analogous arithmetical structures that … view at source ↗
Figure 2
Figure 2. Figure 2: The modified weight parameters of A ∞ 1 . The next figure contains the plot of the modified weight parameters of A ∞ 0 with respect to k0, p0 and n0 . In this figure we have only one type of waves. ✂ ✂❇❇ ✂ ✂❇❇ ✂ ✂❇❇ ✂ ✂❇❇ ✂ ✂❇❇ ✂ ✂❇❇ ✂ ✂❇❇ ✂ ✂❇❇ ✂ ✂❇❇ ✂ ✂❇❇ i 80 w∗ i 1 ✻ ✲ [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The modified weight parameters of A ∞ 0 . PART 3. In Section 28 we define and derive basic properties of shift symmetric vectors. Suppose A∞ = A∞ p (Q) where Q ∈ Mp and p ≥ 0. Then we prove in Part 7 that V (A ∞) is the shift symmetric vector denoted C ∞ p (Q), we refer to (46.1). Hence, we can use shift symmetric vectors to determine the least even vector period of V (A ∞). In Section 29 and 30 we derive … view at source ↗
read the original abstract

The objective of this work is to establish a mathematical framework for the study of symmetric shift registers over the field GF(2). The present paper gives a new approach where the symmetric shift registers are represented by associated systems of nonlinear difference equations. Arithmetical progressions will play a central part. This approach clarifies the underlying structures and makes it easier to determine the minimal periods of the sequences generated by the symmetric shift registers. Key words: Shift registers, nonlinear difference equations, periods, arithmetical progressions, GF(2). An open-source implementation of the algorithms presented in this paper is available on GitHub (https://github.com/paalsoreng/symmetric-shift-register). In addition, an interactive web application is provided for experimenting with and evaluating the algorithms in practice (https://paalsoreng.github.io).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper establishes a mathematical framework for symmetric shift registers over GF(2) by representing them as associated systems of nonlinear difference equations in which arithmetical progressions play a central role; the claim is that this representation clarifies underlying structures and simplifies determination of the minimal periods of the generated sequences.

Significance. If the representation is shown to be faithful and the arithmetical-progression structure is proven to recover exact cycle lengths, the approach could supply a systematic algebraic tool for period analysis of symmetric registers that goes beyond standard linear-feedback methods.

major comments (1)
  1. [Abstract / Main construction] The mapping from symmetric shift registers to systems of nonlinear difference equations over GF(2) is asserted without an explicit invariance argument or bijection showing that the representation preserves the exact sequence dynamics and periods. The abstract states that arithmetical progressions govern the solutions and directly yield minimal periods, yet no derivation establishing this recovery is supplied; this step is load-bearing for the central claim.
minor comments (1)
  1. [Implementation note] The open-source GitHub repository and interactive web application are referenced but no concrete examples, verification runs, or comparison with known period tables appear in the text.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and for identifying a point that requires clarification to strengthen the central claims. We address the concern regarding the mapping and the role of arithmetical progressions below, and we will incorporate explicit arguments in the revised version.

read point-by-point responses

  1. Referee: The mapping from symmetric shift registers to systems of nonlinear difference equations over GF(2) is asserted without an explicit invariance argument or bijection showing that the representation preserves the exact sequence dynamics and periods. The abstract states that arithmetical progressions govern the solutions and directly yield minimal periods, yet no derivation establishing this recovery is supplied; this step is load-bearing for the central claim.

    Authors: We agree that an explicit invariance argument and derivation would make the framework more rigorous. In the revised manuscript we will insert a new subsection (Section 2.3) that constructs an explicit bijection between the state vectors of a symmetric shift register and the solution tuples of the associated nonlinear difference equations. The bijection is defined by identifying each register stage with the corresponding variable in the difference system; we prove that the transition map commutes with this identification, thereby preserving the exact sequence dynamics and hence the periods. In addition, we will add Theorem 3.4 in Section 3, which derives the minimal period from the arithmetical-progression structure: the period is shown to be the least common multiple of the lengths of the APs appearing in the recurrence, with a short proof that uses the fact that each AP is periodic with period dividing 2^k-1 for suitable k and that the nonlinear terms do not introduce shorter cycles. These additions directly address the load-bearing step without altering the original results. revision: yes

Circularity Check

0 steps flagged

No circularity detected; new representation framework is self-contained

full rationale

The paper introduces a representation of symmetric shift registers via systems of nonlinear difference equations over GF(2), with arithmetical progressions used to clarify structures and aid minimal period determination. No quoted equations, definitions, or steps in the abstract or description reduce any claimed result to a fitted parameter, self-referential definition, or self-citation chain by construction. The approach builds an independent algebraic framework without evidence that outputs are forced by inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that symmetric shift registers over GF(2) can be faithfully captured by nonlinear difference equations and that arithmetic progressions are the appropriate lens for extracting minimal periods; no free parameters or invented entities are declared in the abstract.

axioms (1)
  • domain assumption Symmetric shift registers are defined and operate over the field GF(2).
    The abstract states the setting is GF(2) without further justification, which is standard but still an imported assumption.

pith-pipeline@v0.9.0 · 5660 in / 1166 out tokens · 25155 ms · 2026-05-19T12:52:11.546688+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

56 extracted references · 56 canonical work pages

  1. [1]

    Observation 39.1.LetA ∞ =A ∞ p (Q) andQ ∞ =C ∞ p (Q) whereQ∈M + p andp≥0

    A crucial observation. Observation 39.1.LetA ∞ =A ∞ p (Q) andQ ∞ =C ∞ p (Q) whereQ∈M + p andp≥0. Supposejis the least even vector period ofQ ∞. Then jis the least even vector period ofV(A ∞) andsum(Q ∞, j) is the minimal period ofA ∞. 28 Proof.By Observation 14.3 we get thatQ∈M p. Moreover, by (46.1) we get thatV(A ∞) =Q ∞. Hence,jis the least even vector...

    work page

  2. [2]

    The following definition will be used to formulate the results

    Reduction results - complete case. The following definition will be used to formulate the results. Supposeα ∗,γ ∗,j ∗ andζ ∗ are positive integers. Letxandybe the least positive integers satisfyingxα ∗ =yζ ∗. Then we define ω(α∗, γ∗, j∗, ζ∗) = (r, ζ) wherer= 2xγ ∗ +yj ∗ andζ=yζ ∗ +r. We suppose in this section that (40.1)Q= (q 1,· · ·, q J , e0)∈M + p and...

    work page

  3. [3]

    SupposeQ∈M + p wherep≥0

    Determination of the periods. SupposeQ∈M + p wherep≥0. LetQ p =QandQ i−1 =π(Q i) for 1≤i≤p. Observation 14.5 implies thatQ i ∈M + i for 0≤i≤p. LetQ ∞ i =C ∞ i (Qi) for 0≤i≤p. We note thatQ ∞ i−1 =C ∞ i−1(π(Qi)) for 1≤i≤p. We also letj 0, j1,· · ·, j p andζ 0, ζ1,· · ·, ζ p be the dynamical parameters ofQ p with respect top. 30 Proposition 41.1.Supposej i−...

    work page

  4. [4]

    We letA r =a r+1 · · ·a r+n forr≥0

    Basic properties. We letA r =a r+1 · · ·a r+n forr≥0. In particular,A 0 =A. Ifj≥0 , then (42.1)a n+j+1 =a ′ j+1 ifk≤w(a j+2 · · ·a j+n)≤k+p, anda n+j+1 =a j+1 otherwise. We also letw r =w(a r+1 · · ·a r+n)−k=w(A r)−kforr≥0. By (3.1) we get thatw r =a r+1 +· · ·+a r+n −kforr≥0. Ifa r+1 = 1 wherer≥0, then (42.2)a r+n+1 =a ′ r+1 ⇔k≤w(a r+2 · · ·a r+n)≤k+p ⇔k...

    work page

  5. [5]

    SupposeA=a 1 · · ·a n wherea 1 = 1

    Positive start strings. SupposeA=a 1 · · ·a n wherea 1 = 1. LetPbe a start string ofAsatisfying w(P) =p+ 1 and 0< w(S)≤p+ 1 for each start stringS̸= Ø ofP. Then we callPa positive start string ofAof orderp+1. We also suppose the last bit ofPis 1. We will prove thatV(A)∈M + p . We note thatV(A)∈M. SupposeV(A) = (v 1,· · ·, v J , vJ+1). ThenA= 1 v10v2 · · ·...

    work page

  6. [6]

    Observation 44.1.Supposer≥0

    Auxiliary results. Observation 44.1.Supposer≥0. a) Suppose 0< w r < p+ 1. Thena r+n+1 =a ′ r+1 andw r+1 =w r − w(ar+1). b) Supposew r+1 < w r. Thena r+1 = 1 andw r+1 =w r −1 =w r − w(ar+1). Proof.a) Ifa r+1 = 1, then (42.5) implies thatw r+1 =w r −1 =w r −w(ar+1). Ifa r+1 = 0, then (42.7) implies thatw r+1 =w r + 1 =w r − w(ar+1). b) By Observation 42.1 a...

    work page

  7. [7]

    SupposeA=a 1 · · ·a n wherea 1 = 1

    The infinite vector representation. SupposeA=a 1 · · ·a n wherea 1 = 1. LetA ∞ =a 1 · · ·a nan+1 · · ·be generated fromAby the symmetric shift registerθwith parametersk,pandn, and supposew(A) =k+p+ 1. Sincea 1 = 1, thena 2 +· · ·+a n =k+p. Hence, an+1 =a ′ 1 = 0. As in Section 6 we decompose (45.1)A ∞ = 1q10q21q3 · · ·whereq i ≥1 fori≥1. The vector repres...

    work page

  8. [8]

    LetA ∞ =A ∞ p (Q) whereQ∈M p andp≥0

    A crucial representation. LetA ∞ =A ∞ p (Q) whereQ∈M p andp≥0. ThenA ∞ is generated as in Section 18 fromA=A(Q) by the symmetric shift register with respect to the parametersk=w(A)−(p+ 1),pandn=length(A). Thenw(A) =k+p+ 1 andAstarts with 1. In the next section we will prove that (46.1)C ∞ p (Q) =V(A ∞). SupposeA ∞ =a 1 · · ·a nan+1 · · ·andV(A ∞) = (q1, q...

    work page

  9. [9]

    Letλ j =w rj forj≥0

    Deductions. Letλ j =w rj forj≥0. Thenλ 0 =w r0 =p+ 1. Moreover, let (47.1)s j+1 =min{q j+1, λj}=min{q j+1, wrj }ifj≥0 is even, (47.2)s j+1 =min{q j+1, p+ 1−λ j}=min{q j+1, p+ 1−w rj }ifj≥0 is odd, (47.3)e j+1 =q j+1 −s j+1 forj≥0. Observation 47.1.Supposej≥0. Then 0< λ j ≤p+ 1 ifjis even, and 0≤λ j < p+ 1 ifjis odd. Proof.Follows from Observation 46.3 sin...

    work page

  10. [10]

    SupposeQ ∞ = (q 1, q2,· · ·) is complete

    Uniqueness properties. SupposeQ ∞ = (q 1, q2,· · ·) is complete. Letπ(Q ∞) = (q ∗ 1, q∗ 2,· · ·) be the contraction vector andD ∞ = (d1, d2,· · ·) the distance vector ofQ ∞. Letτ be the distance function ofQ ∞. Letr 0, r1,· · ·andt 1, t2,· · ·be ther-indexes andt-indexes ofQ ∞. We also letβ i =τ(r i) andy i =y(r i) fori≥0. Moreover, lett max(r) andnext(r)...

    work page

  11. [11]

    Supposej≥1

    Deductions. Supposej≥1. Moreover, supposeq rj +r =q r forr≥1. We will prove that dyj +i =d i+βj andq ∗ j+i =q ∗ i fori≥1. We refer to Observation 49.5 and 49.6. Observation 49.1.τ(r j +i) =β j +τ(i) fori≥0. Proof.Ifi= 0, this is trivial. Otherwise, ifi >0, then (32.8) implies that τ(r j +i) =τ(r j) +δ(q rj +1,· · ·, q rj +i) =β j +δ(q 1,· · ·, q i) =β j +...

    work page

  12. [12]

    In this section we supposej≥1 and (50.1)d yj +i =d i +β j andq ∗ j+i =q ∗ i fori≥1

    Additional deductions. In this section we supposej≥1 and (50.1)d yj +i =d i +β j andq ∗ j+i =q ∗ i fori≥1. We will prove in the end of this section thatq rj +r =q r forr≥1. We refer to Observation 50.7 b). By Observation 37.5 a) we get thatβ j >0. Sinced yj +1 =d 1 +β j > d 1, theny j ≥1. By (37.1) we get thaty i =r(D ∞, βi) fori≥0. Supposei≥0. Then we ge...

    work page

  13. [13]

    In this part we supposep≥0,Q= (q 1,· · ·, q J , e0)∈M, andQ ∞ =C ∞ p (Q) is the shift symmetric vector generated byQwith respect top

    Assumptions and basic properties. In this part we supposep≥0,Q= (q 1,· · ·, q J , e0)∈M, andQ ∞ =C ∞ p (Q) is the shift symmetric vector generated byQwith respect top. We also supposeQ ∞ = (q1, q2,· · ·). Let (s 1, s2,· · ·), (e 0, e1,· · ·) and (λ 0, λ1,· · ·) be the associated sequences. Thenλ 0 =p+ 1. By Observation 28.4 we get thatq j+1 >0 forj≥0. Sin...

    work page

  14. [14]

    In this section we letτbe the distance function ofQ ∞ defined byτ(0) = 0 andτ(r) =q − 1 +· · ·+q − r forr≥1

    Properties of the distance function. In this section we letτbe the distance function ofQ ∞ defined byτ(0) = 0 andτ(r) =q − 1 +· · ·+q − r forr≥1. SinceQ= (q 1,· · ·, q J , e0) whereq i >0 for 1≤i≤Jande 0 ≥0, then (52.1)α=δ(Q) + 1 =q − 1 +· · ·+q − J +e − 0 + 1 =τ(J) +e 0 ≥τ(J). By (28.8) and (28.9) we get that (52.2)q − J+i+1 −q − i+1 =e i +s − i+1 −(s − ...

    work page

  15. [15]

    In this section we supposer≥0,t≥0 andq r+2i = 1 for 1≤i≤t

    Properties of theλ- parameters. In this section we supposer≥0,t≥0 andq r+2i = 1 for 1≤i≤t. By Observation 51.1 b) we get thats r+2i = 1 for 1≤i≤t. Observation 53.1.Suppose 0≤i≤2twhereiis odd. Thens r+i+1 = 1. Proof.Sinceiis odd andi+ 1 is even, then 1≤i <2tandi+ 1 = 2i ∗ where 1≤i ∗ ≤t. Hence,s r+i+1 =s r+2i∗ = 1. Observation 53.2.Supposeris even. Let 1≤i...

    work page

  16. [16]

    We letf 2i =q 2i+1 +q 2i+3 +q 2i+5 +· · ·+q 2i+J fori≥0

    Periodic properties. We letf 2i =q 2i+1 +q 2i+3 +q 2i+5 +· · ·+q 2i+J fori≥0. Ifi≥0, then (54.1)f 2(i+1) =q 2i+3 +q 2i+5 +· · ·+q 2(i+1)+J =f 2i +q 2(i+1)+J −q 2i+1. Observation 54.1.Supposei≥0. a)λ 2(i+1) =λ 2i+2 =λ 2i+1 +s 2i+2 =λ 2i −s 2i+1 +s 2i+2. b)f 2(i+1) =f 2i +q 2(i+1)+J −q 2i+1 =f 2i −s 2i+1 +s 2i+2. c)f 2(i+1) −λ 2(i+1) =f 2i −λ 2i. Proof.a) f...

    work page

  17. [17]

    SupposeD ∞ = (d1, d2,· · ·) where (55.1) 0< d 1 ≤d 2 ≤d 3 ≤ · · ·andd j → ∞ifj→ ∞

    Assumptions and definitions. SupposeD ∞ = (d1, d2,· · ·) where (55.1) 0< d 1 ≤d 2 ≤d 3 ≤ · · ·andd j → ∞ifj→ ∞. Letr(D ∞, β) = #{i≥1 :d i ≤β}forβ >0. Ify≥1, then (55.1) implies that (55.2)r(D ∞, β) =y⇔d y ≤β < d y+1. We callβ >0 a progression parameter ofD ∞ if (55.3)d y+i =d i +βfori≥1, wherey=r(D ∞, β). Theny >0, sinced y+1 =d 1 +β > d 1

    work page

  18. [18]

    Supposeβandβ ∗ are progression parameters ofD ∞

    Basic properties. Supposeβandβ ∗ are progression parameters ofD ∞. Lety=r(D ∞, β) andy ∗ =r(D ∞, β∗). Then (56.1)d y+i =d i +βandd y∗+i =d i +β ∗ fori≥1. We note thaty≥1 andy ∗ ≥1. Moreover, by (55.2) we get that (56.2)d y ≤β < d y+1 andd y∗ ≤β ∗ < d y∗+1. Observation 56.1.β+β ∗ is a progression parameter ofD ∞ and r(D∞, β+β ∗) =y+y ∗. Proof.By (56.1) and...

    work page

  19. [19]

    In this section we supposeα >0 is a progression parameter ofD ∞

    Least progression parameters. In this section we supposeα >0 is a progression parameter ofD ∞. Then (57.1)d γ+i =d i +αfori≥1, whereγ=r(D ∞, α). We note thatγ >0 and 0< d 1 ≤d 2 ≤ · · · ≤d γ ≤α < d γ+1 ≤ · · ·. LetD= (d 1,· · ·, d γ). Moreover, letα ∗ andγ ∗ be the least progression parameters ofDwith respect toα. In the end of this section we will prove:...

    work page

  20. [20]

    We supposep >0 andQ ∞ =C ∞ p (Q) is the shift symmetric vector generated byQ= (q 1,· · ·, q J , e0)∈M + p with respect top

    Assumptions and notation. We supposep >0 andQ ∞ =C ∞ p (Q) is the shift symmetric vector generated byQ= (q 1,· · ·, q J , e0)∈M + p with respect top. We also supposeD(Q)̸= Ø. LetQ ∞ = (q 1, q2,· · ·), and let (s 1, s2,· · ·), (e 0, e1,· · ·) and (λ 0, λ1,· · ·) be the associated sequences. In particular,λ 0 =p+ 1. By Observation 14.3 and 14.4 we get thatQ...

    work page

  21. [21]

    We supposer 0, r1, r2,· · ·andt 1, t2,· · ·are ther- andt- indexes ofQ ∞

    Ther- andt-indexes. We supposer 0, r1, r2,· · ·andt 1, t2,· · ·are ther- andt- indexes ofQ ∞. We chooseImaximal such thatr I ≤J. By (33.1) we get that (59.1)r 0 = 0< r 1 <· · ·< r I ≤J < r I+1 <· · · wherer j+1 =next(r j) forj≥0. Moreover,t j+1 =t max(rj) forj≥0. 47 We also letz 0 ≥0 be maximal such thatr I + 2z0 ≤J. Thenr I +2z 0 =J−1 orr I + 2z0 =J. We ...

    work page

  22. [22]

    Ifj≥0, then (33.3) and Observation 51.1 b) imply that (60.1)q rj +2i =s rj +2i = 1 ande rj +2i = 0 for 1≤i≤t j+1

    Properties of theλ- parameters. Ifj≥0, then (33.3) and Observation 51.1 b) imply that (60.1)q rj +2i =s rj +2i = 1 ande rj +2i = 0 for 1≤i≤t j+1. Ifs rj +1 >1 wherej≥0, then Observation 28.4 implies that (60.2)s rj +i ≥1 fori≥2, ands − rj +1 +· · ·+s − rj +i >0 fori≥1. Supposej≥0. By (33.4) and Observation 28.3 b) we get that (60.3)r j is even ifjis even,...

    work page

  23. [23]

    Forj≥0 we letm j+1 be the maximal integer such that (61.1) 0≤m j+1 ≤t j+1 ande rj +i = 0 for 1≤i≤2m j+1

    Additional parameters and results. Forj≥0 we letm j+1 be the maximal integer such that (61.1) 0≤m j+1 ≤t j+1 ande rj +i = 0 for 1≤i≤2m j+1. We also letz j+1 =t j+1 −m j+1 forj≥0. Ifj≥0, then (61.2)t j+1 =m j+1 +z j+1 wherem j+1 ≥0 andz j+1 ≥0, (61.3)r j + 2mj+1 + 2zj+1 + 1 =r j + 2tj+1 + 1 =r j+1, (61.4)q rj +i =s rj +i for 1≤i≤2m j+1, where (61.2) is tri...

    work page

  24. [24]

    Observation 62.1.Supposee rj +2mj+1 +1 >0 wherej≥0 is even

    The even case. Observation 62.1.Supposee rj +2mj+1 +1 >0 wherej≥0 is even. Then λrj +2i+1 = 0 form j+1 ≤i≤t j+1, ands rj +2i+1 = 1 form j+1 < i≤t j+1. Proof.By (60.3) we get thatr j andr j + 2mj+1 are even. Hence, (28.3) and Observation 51.2 a) imply thatsrj +2mj+1 +1 < q rj +2mj+1 +1 andλ rj +2mj+1 +1 = 0. Next, we supposeλ rj +2i+1 = 0 wherem j+1 ≤i < t...

    work page

  25. [25]

    Observation 63.1.Supposee rj +2mj+1 +1 >0 wherej≥0 is odd

    The odd case. Observation 63.1.Supposee rj +2mj+1 +1 >0 wherej≥0 is odd. Then λrj +2i+1 =p+ 1 form j+1 ≤i≤t j+1, ands rj +2i+1 = 1 form j+1 < i≤t j+1. Proof.By (60.3) we get thatr j andr j + 2mj+1 are odd. Then (28.3) and Observation 51.2 b) imply thats rj +2mj+1 +1 < q rj +2mj+1 +1 andλ rj +2mj+1 +1 = p+ 1. Supposeλ rj +2i+1 =p+ 1 wherem j+1 ≤i < t j+1. ...

    work page

  26. [26]

    Observation 64.1.Supposem j+1 < t j+1 wherej≥0

    Properties of the parameters. Observation 64.1.Supposem j+1 < t j+1 wherej≥0. Thens rj +2i+1 = 1 form j+1 < i≤t j+1, ands rj +i = 1 for 2m j+1 + 1< i≤2t j+1 + 1. Proof.Observation 61.1 implies thate rj +2mj+1 +1 >0. Hence, the results follow from (60.1), Observation 62.1 and 63.1. Proposition 64.2.Supposej≥0. a)q rj +J+2i = 1 for 1≤i≤m j+1. b)q rj +J+2i+1...

    work page

  27. [27]

    We prove in the end of this section that (65.1)r I+j =r j−1 +J+ 2m j + 1 andt I+j =z j−1 +m j forj≥1

    Crucial results. We prove in the end of this section that (65.1)r I+j =r j−1 +J+ 2m j + 1 andt I+j =z j−1 +m j forj≥1. Observation 65.1.Supposej≥0,t≥0,q rj +2i = 1 for 1≤i≤t, andq rj +2t+2 >1. Thent j+1 =tandr j+1 =r+ 2t+ 1. Proof.We note thatt=t max(rj) =t j+1. Hence, by (33.2) we also get that rj+1 =r j + 2tj+1 + 1 =r+ 2t+ 1. Observation 65.2.a)q rI +2i...

    work page

  28. [28]

    Observation 66.1.Supposer≥0 is even andr̸=r j for eachj≥0

    Properties of the even vector periods. Observation 66.1.Supposer≥0 is even andr̸=r j for eachj≥0. Then qr+1 = 1 orλ r ≤p. Proof.By (33.1) there existsj≥0 such thatr j < r < r j+1. By (33.2) we get thatr j+1 =r j + 2tj+1 + 1. There existsisuch thatr=r j + 2i−1 orr=r j + 2iwhere 1≤i≤t j+1. Ifr=r j + 2i−1, then we get according to (33.3) thatq r+1 =q rj +2i ...

    work page

  29. [29]

    Letc 0 = 0< c 1 < c 2 <· · ·be thec- indexes ofQ ∞ = (q1, q2,· · ·), and letτ be the distance function ofQ ∞

    Properties of the distance vector. Letc 0 = 0< c 1 < c 2 <· · ·be thec- indexes ofQ ∞ = (q1, q2,· · ·), and letτ be the distance function ofQ ∞. The distance vector ofQ ∞ is given by (67.1)D ∞ = (d1, d2,· · ·) whered i =τ(c i) fori≥1. Sincec 1 is the least index> c 0 + 1 = 1 such thatq c1 = 1, then (58.4) implies thatc 1 ≤J. Letα=δ(Q) + 1 andγ=r(D ∞, α). ...

    work page

  30. [30]

    As in Section 37 we supposey j =y(r j) forj≥0

    Notation and auxiliary results. As in Section 37 we supposey j =y(r j) forj≥0. According to (35.8), and Observation 37.1 b) we get that (68.1)y j+1 =y j +t j+1 andc yj ≤r j < c yj +1 forj≥0. 52 According to Observation 37.1 a), 37.2 and 37.4 a) we get that (68.2)c yj +i =r j + 2iandd yj +i =τ(r j + 2i) for 1≤i≤t j+1 andj≥0, (68.3)y 0 = 0≤y 1 ≤y 2 ≤ · · ·a...

    work page

  31. [31]

    Letτ Q be the distance vector ofQ= (q 1,· · ·, q J , e0)

    The distance vector ofQ. Letτ Q be the distance vector ofQ= (q 1,· · ·, q J , e0). SinceQ ∞ = (q1, q2,· · ·), thenτ Q(c) =τ(c) for 0≤c≤J. By Observation 68.2 we get that (69.1)c 0 = 0< c 1 < c 2 <· · ·< c γ ≤J < c γ+1 < c γ+2 <· · ·. Proposition 69.1.D(Q) = (d 1,· · ·d γ). Proof.a) By (35.2) and (69.1) we get thatc 0 = 0< c 1 < c 2 <· · ·< c γ ≤J, ci+1 is...

    work page

  32. [32]

    Observation 70.1.γ+y j =y I+j +z j forj≥0

    Arithmetical properties. Observation 70.1.γ+y j =y I+j +z j forj≥0. Proof.Sincey 0 = 0, we get from Observation 68.2 thatγ+y 0 =y I+0 +z 0. Ifγ+y j =y I+j +z j wherej≥0, then (61.2), (65.1) and (68.1) imply that γ+y j+1 =γ+y j +t j+1 =y I+j +z j +m j+1 +z j+1 =y I+j +t I+j+1 +z j+1 =y I+j+1 +z j+1. 53 Observation 70.2.Supposej≥0. a)τ(r j +J+ 2i) =τ(r j + ...

    work page

  33. [33]

    LetQ ∗ =π(Q) andQ ∞ ∗ =π(Q ∞) be the contraction vectors ofQandQ ∞

    Properties of the contraction vectors. LetQ ∗ =π(Q) andQ ∞ ∗ =π(Q ∞) be the contraction vectors ofQandQ ∞. By (33.6) we get that (71.1)Q ∞ ∗ = (q∗ 1, q∗ 2,· · ·) whereq ∗ j+1 =τ(r j+1)−τ(r j) forj≥0. By (33.1) we get thatr 0 = 0< r 1 < r 2 <· · ·. We decompose (71.2)Q ∞ = (G1, G2,· · ·) whereG j+1 = (qrj +1,· · ·, q rj+1) forj≥0. Then we get by (32.8) and...

    work page

  34. [34]

    As in Section 59 letIbe maximal such thatr I ≤J

    The contraction vector ofQ. As in Section 59 letIbe maximal such thatr I ≤J. By (33.1) we get that (72.1)r 0 = 0< r 1 <· · ·< r I ≤J < r I+1 <· · ·. LetQ ∗ =π(Q). By (72.1) we can decomposeQ= (q 1,· · ·, q J , e0) as (72.2)Q= (G 1,· · ·, G I, F0) whereG j+1 = (qrj +1,· · ·, q rj+1) for 0≤j < I. 55 By Observation 59.1 we get thatIis odd. In particularI >0,...

    work page

  35. [35]

    Supposej≥0

    Crucial relations. Supposej≥0. Then (73.1)q ∗ j+1 =q − rj +1 +· · ·+q − rj +2tj+1 +1 ands ∗ j+1 =s − rj +1 +· · ·+s − rj+2tj+1 +1, (73.2)s rj +i ≤q rj +i fori≥1, ands ∗ j+1 ≤q ∗ j+1, where (73.1) follows from (33.2), (71.3) and (71.6), and (73.2) from (28.5). Observation 73.1.a)s ∗ j+1 =s − rj +1 +· · ·+s − rj +2mj+1 +1 forj≥0. b)s ∗ j+1 =q − rj +1 +· · ·...

    work page

  36. [36]

    Observation 74.1.Ife rj +2mj+1 +1 = 0 wherej≥0, thens ∗ j+1 =q ∗ j+1

    Deductions. Observation 74.1.Ife rj +2mj+1 +1 = 0 wherej≥0, thens ∗ j+1 =q ∗ j+1. Proof.Supposee rj +2mj+1 +1 = 0 wherej≥0. By Observation 61.1 we get thatm j+1 =t j+1. Moreover, we get according to (28.3) and (61.4) thats rj +2mj+1 +1 =q rj +2mj+1 +1 ands rj +i =q rj +i for 1≤i≤2m j+1. Sincem j+1 =t j+1, we conclude thats rj +i =q rj +i for 1≤i≤2t j+1 + ...

    work page

  37. [37]

    =e ∗ 0 +s ∗ 1. Letj≥1. By (71.3), Observation 73.2 and (71.10) we get that q∗ I+j+1 =τ(r I+j+1)−τ(r I+j) = (τ(r j) +s ∗ j+1 +α)−(τ(r j−1) +s ∗ j +α). = (τ(r j)−τ(r j−1))−s ∗ j +s ∗ j+1 =q ∗ j −s ∗ j +s ∗ j+1 =e ∗ j +s ∗ j+1. PART 12. We supposeA ∞ =a 1a2 · · ·is generated fromA=a 1 · · ·a n by the symmetric shift registerθwith parametersk,pandnwherek≤w(A)...

    work page

  38. [38]

    In this section we supposer≥0

    Properties of the weight parameters. In this section we supposer≥0. By Observation 42.1 a) we get that (75.1) 0≤w r ≤p+ 1 and 0≤w r+n ≤p+ 1. The next observations follow from (42.5),· · ·, (42.8) and (75.1). Observation 75.1.Supposea r+1 = 1,w r >0 andw r+n >0. a) Ifw r+n < p+ 1, thenw r+1 =w r −1,a r+n+1 = 0 andw r+n+1 =w r+n + 1. b) Ifw r+n =p+ 1, thenw...

    work page

  39. [39]

    Observation 76.1.Suppose 0< m < p+ 1,b r =w r +w r+n andr≥0

    Auxiliary results. Observation 76.1.Suppose 0< m < p+ 1,b r =w r +w r+n andr≥0. a) Ifb r ≥m+p+ 1 , thenm≤w r ≤p+ 1 andm≤w r+n ≤p+ 1. b) Ifb r ≤m, then 0≤w r ≤mand 0≤w r+n ≤m. 58 Proof.Sinceb r =w r +w r+n, the results follow from (75.1). Observation 76.2.a) IfA r+z =A r wherez >0, thenzis a period ofA ∞. b) Ifzis period ofA ∞, thenA i+z =A i andw i+z =w i...

    work page

  40. [40]

    We suppose in this section that 0< m < p+ 1

    Basic results. We suppose in this section that 0< m < p+ 1. We define B+ m ={r≥0 :b r ≥m+p+ 1 andw r+i ≥mfor 1≤i≤n}, B− m ={r≥0 :b r ≤mandw r+i ≤mfor 1≤i≤n}. Observation 77.1.Supposer∈B + m andb r+1 ≥m+p+1. Thenr+1∈B + m. Proof.It is sufficient to prove thatw r+1+i ≥mfor 1≤i≤n. Sinceb r+1 ≥m+p+ 1, then Observation 76.1 a) implies thatw r+1+n ≥m. Moreover,...

    work page

  41. [41]

    Letx=min{w i : 0≤i≤2n}andy=max{w i : 0≤i≤2n}

    The determination of upper and lower bounds. Letx=min{w i : 0≤i≤2n}andy=max{w i : 0≤i≤2n}. Proposition 78.1.min{w i :i≥0}=xandmax{w i :i≥0}=y. 60 Proof.It is sufficient to prove thatx≤w i ≤yfori≥0. By (75.1) we note that 0≤x < y≤p+ 1. The proof is divided into 4 subcases. 1)Ifx= 0 andy=p+ 1, then (75.1) implies thatx≤w i ≤yfori≥0. 2)Suppose 0< x < y < p+ ...

    work page

  42. [42]

    Adjustment of the parameters. We will determine parametersk ∗ ≥0 andp ∗ ≥0 such that (79.1)min{w(A i) :i≥0}=k ∗ andmax{w(A i) :i≥0}=k ∗ +p ∗ + 1, andA ∞ =a 1a2 · · ·is generated fromA=a 1 · · ·a n by the symmetric shift register with parametersk ∗,p ∗ andn. Letx=min{w i : 0≤i≤2n}andy=max{w i : 0≤i≤2n}. According to Proposition 78.1 we get that (79.2)min{w...

    work page

  43. [43]

    Supposemin{w(A i) :i≥0}=kandmax{w(A i) :i≥0}=k+p+ 1

    A crucial algorithm. Supposemin{w(A i) :i≥0}=kandmax{w(A i) :i≥0}=k+p+ 1. By Section 79 we can always transfer the determination of minimal periods to this case. We get thatmin{w i :i≥0}= 0 andmax{w i :i≥0}=p+ 1. Algorithm 80.1.Letsbe the least integer≥0 such thatw s =p+ 1. Lett > sbe minimal such thatw t = 0. Letrbe maximal such thats≤r < t andw r =p+ 1....

    work page

  44. [44]

    LetV= (v 1,· · ·, v J+1)∈M ∗, and letτbe the distance function ofV

    Assumptions and notation. LetV= (v 1,· · ·, v J+1)∈M ∗, and letτbe the distance function ofV. Then (81.1)Jis odd,v 1 >1,v i ≥1 for 2≤i≤J, andv J+1 ≥0, (81.2)v − i ≥0 for 1≤i≤J, andv − J+1 + 1≥0, (81.3) 0< τ(1)≤τ(2)≤ · · · ≤τ(J). If 0≤r≤J, lett max(r) =tandnext(r) =r+ 2t+ 1 =r+ 2t max(r) + 1 wheret≥0 is maximal such thatr+ 2t≤Jandv r+2i = 1 for 1≤i≤t. Letr...

    work page

  45. [45]

    Observation 82.1.Suppose 0≤j≤I, 0≤i≤2t j+1 andiis odd

    Auxiliary results. Observation 82.1.Suppose 0≤j≤I, 0≤i≤2t j+1 andiis odd. Then vrj +i+1 = 1,v − rj +i+1 = 0 andτ(r j +i+ 1) =τ(r j +i) +v − rj +i+1 =τ(r j +i). Proof.Sinceiis odd andi+ 1 is even, then 1≤i <2t j+1 andi+ 1 = 2i ∗ where 1≤i ∗ ≤t j+1. Hence, (81.5) implies thatv rj +i+1 =v rj +2i∗ = 1. Observation 82.2.Suppose 0≤i≤2t j+1 + 1 where 0≤j≤Iandjis...

    work page

  46. [46]

    Letρ ∗ 0,· · ·, ρ ∗ I+1 be the alternating parameters ofπ(V) = (v ∗ 1,· · ·, v ∗ I+1)

    The alternating parameters ofπ(V). Letρ ∗ 0,· · ·, ρ ∗ I+1 be the alternating parameters ofπ(V) = (v ∗ 1,· · ·, v ∗ I+1). Thenρ ∗ 0 = 0 andρ ∗ 1 =ρ ∗ 0 +v ∗ 1 =v ∗

    work page

  47. [47]

    Observation 83.1.Suppose 0≤j≤I

    If 0≤i≤I, then by (14.1) we get that (83.1)ρ ∗ i+1 =ρ ∗ i +v ∗ j+1 ifiis even, andρ ∗ i+1 =ρ ∗ i −v ∗ i+1 ifiis odd. Observation 83.1.Suppose 0≤j≤I. Thenρ rj =ρ ∗ j ifjis even, andρ rj =ρ ∗ j + 1 ifjis odd. Proof.Sincer 0 = 0, thenρ ∗ 0 = 0 =ρ 0 =ρ r0. Suppose this is true forj where 0≤j < I. Then (83.1) and Observation 82.4 imply that ρrj+1 =ρ rj +v ∗ j+...

    work page

  48. [48]

    We will prove the following result

    The main result. We will prove the following result. (84.1) IfV∈M + p wherep >0, thenπ(V) = (v ∗ 1,· · ·, v ∗ I+1)∈M + p−1 =M + p∗ wherep ∗ =p−1. SupposeV= (v 1,· · ·, v J+1)∈M + p wherep >0. By Observation 14.4 we get thatV∈M ∗. Hence, by Proposition 81.2 we also get thatπ(V)∈M. According to Section 14 it is therefore sufficient to prove that (84.2)π(V) ...

    work page

  49. [49]

    Drazin & R.S

    P.G. Drazin & R.S. Johnson, Solitons: an introduction, Cambridge, 1989

    work page 1989

  50. [50]

    Helleseth, Nonlinear Shift Registers, Survey and open problems, Algebraic Curves and Finite Fields, De Gruyter, 2014

    T. Helleseth, Nonlinear Shift Registers, Survey and open problems, Algebraic Curves and Finite Fields, De Gruyter, 2014

    work page 2014

  51. [51]

    Kjeldsen, On the cycle structure of a set of nonlinear shift registers with symmetric feedback functions, J

    K. Kjeldsen, On the cycle structure of a set of nonlinear shift registers with symmetric feedback functions, J. Combinatorial Theory, Ser. A., 20 (1976), page 154-169

    work page 1976

  52. [52]

    Mykkeltveit, Nonlinear recurrences and arithmetic Codes, Information and control, Vol

    J. Mykkeltveit, Nonlinear recurrences and arithmetic Codes, Information and control, Vol. 33 (1977), page 193-209

    work page 1977

  53. [53]

    Mykkeltveit, M

    J. Mykkeltveit, M. K. Siu, and P. Tong, On the cycle structure of some nonlinear shift register sequences, Information and control, Vol. 43 (1979), page 202-215

    work page 1979

  54. [54]

    Søreng, The periods generated by some symmetric shift registers, J

    J. Søreng, The periods generated by some symmetric shift registers, J. Combinatorial Theory, Ser. A., 21 (1976), page 165-187

    work page 1976

  55. [55]

    Søreng, Symmetric shift registers, Pacific J

    J. Søreng, Symmetric shift registers, Pacific J. Math., 85 (1979), page 201-229

    work page 1979

  56. [56]

    Søreng, Symmetric shift registers, Pacific J

    J. Søreng, Symmetric shift registers, Pacific J. Math., 98 (1982), page 203-234. 67 Index Section Section A′,w(A) and w(A) 3A ∞ p (Q) 18 #V,sum(V) andsum(V, j) 4 cyclic parameters 20 V+αandV−α4ψ20 extension of vectors 4 dynamical parameters 21 θ5 weight parameters,w i, w∗ i 27 V(A ∞) 6 shift symmetric vector,C ∞ p (Q) 28 M,M ∗ andM p 7λ j,s j+1 ande j 28 ...

    work page 1982