Timeline for Why do some linear cellular automata over $Z_{2}$ on the torus have small order?
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 6, 2019 at 20:37 | comment | added | Joseph Van Name | Disregard my previous three comments. My answer shows that the low periodicity phenomenon holds for characteristic $p$ where the cellular automata is over an abelian $p$-group. In other words, the low periodicity holds for all characteristics $p$ and all dimensions. | |
| Jan 6, 2019 at 20:34 | vote | accept | Joseph Van Name | ||
| Jan 6, 2019 at 20:28 | answer | added | Joseph Van Name | timeline score: 0 | |
| Dec 8, 2017 at 18:51 | comment | added | Joseph Van Name | So the phenomenon does not depend on whether one uses Block cellular automata or not. It seems to hold for all reversible linear cellular automata over $F_{2}$ over the torus of dimensions 1 or 2. | |
| Nov 21, 2017 at 18:24 | answer | added | GNiklasch | timeline score: 2 | |
| Nov 21, 2017 at 17:52 | answer | added | GNiklasch | timeline score: 1 | |
| Nov 6, 2017 at 21:04 | answer | added | Ilmari Karonen | timeline score: 3 | |
| Oct 24, 2017 at 15:14 | review | Close votes | |||
| Oct 25, 2017 at 0:23 | |||||
| Oct 16, 2017 at 17:58 | comment | added | Joseph Van Name | The phenomenon holds in the generalization where there are four different rules where the generations alternate between several different rules. Furthermore, if the period where the grid size is $2m\times 2m$ is $p$, then the period where the grid size is $4m\times 4m$ is $2p$. | |
| Oct 16, 2017 at 13:00 | comment | added | Joseph Van Name | My computer experiments show that this phenomenon does not hold for finite fields of characteristic greater than 2. | |
| Oct 16, 2017 at 6:29 | comment | added | Ilmari Karonen | @GNiklasch: Yes, $2p$ is clearly just the LCM of the periods of all the possible initial conditions on the 2×2 grid, which is easily obtained directly from the rule table. (By linearity, it's sufficient to consider only the orbits containing any four orthogonal states, such as those having one cell on and others off.) I believe the full result should follow by induction on $n$, but my proof sketch has a gap: all works great if I assume that certain matrices over $\mathbf F_2$ commute, and for "traditional" CA translation invariance should imply it, but the Margolus grid is throwing me off. :( | |
| Oct 13, 2017 at 17:21 | comment | added | GNiklasch | Here's an idea - I haven't yet had time to work out the details. Firstly, linearity is special (most of the predefined rules aren't: "Swap on Diag" is, and is one of the simplest examples, and visually boring). Second, when you have a linear rule, you can take cell coordinates mod 2 and look at the induced action (with the same rule!) on a 2x2 grid. And then decompose the upstairs action into a part lifted from downstairs and a translation-by-blocks part. Your $p$ will come from the induced permutation of the 16 states of the 2x2 grid (after two steps: one for each block position/phase). | |
| Oct 13, 2017 at 2:52 | comment | added | Kim Morrison | @JosephVanName, I'd suggest that asking here in the comments is unlikely to get a useful response, and indeed only likely to attract further trouble. If you flag questions where you think there has been inappropriate downvoting, we'll look into it (as we currently are for a recent flag you made). | |
| Oct 13, 2017 at 2:50 | comment | added | Joseph Van Name | Can the downvoter please explain what is wrong with this question or is it the same old story as always? | |
| Oct 12, 2017 at 13:58 | comment | added | GNiklasch | After some playing with the emulator, and without knowledge of prior research, my impression is that other reversible rules (such as "Rotation", the first canned one) may have much longer periods. Your example does seem to hit a special case. It is even more special: after a half period, it replicates the input pattern but translated to the antipode on the torus (e.g. shifted by (32,32) on a 64x64 grid). Is this rule perhaps invariant under some kind of scaling transformation - some discrete analogue of inflation/deflation...? | |
| Oct 12, 2017 at 13:49 | comment | added | GNiklasch | For the benefit of readers looking for some background information, the Wikipedia article Block cellular automaton provides a nice overview. | |
| Oct 12, 2017 at 2:05 | history | asked | Joseph Van Name | CC BY-SA 3.0 |