Ternary parallelogram scales are MOS substitution: Difference between revisions
| Line 44: | Line 44: | ||
By the previous step, φ restricted to any ''m'' × ''n'' window in ℤ<sup>2</sup> is surjective, hence all of the four windows ''Q''<sub>1</sub>, ..., ''Q''<sub>4</sub> have 1 somewhere in them. Call these positions '''u'''<sub>1</sub>, ..., '''u'''<sub>4</sub> (note that none of them are the zero vector). Since {{Nowrap|φ((0, 0)) {{=}} 0}} by another application of the previous step we have '''u'''<sub>1</sub>, ..., '''u'''<sub>4</sub> as the images of 1-step vectors of ''w''. Since ''w'' is ternary, exactly two of these vectors will be pairwise equal, say '''u'''<sub>''k''</sub> = '''u'''<sub>''l''</sub>. These four "quadrants" intersect in <math>[-m + 1 : m] \times \{0\} \cup \{0\} \times [-n + 1 : n],</math> entailing that '''u'''<sub>''k''</sub> = '''u'''<sub>''l''</sub> is on a coordinate axis (either the '''v'''-coordinate is 0 or the '''w'''-coordinate is 0 but not both). | By the previous step, φ restricted to any ''m'' × ''n'' window in ℤ<sup>2</sup> is surjective, hence all of the four windows ''Q''<sub>1</sub>, ..., ''Q''<sub>4</sub> have 1 somewhere in them. Call these positions '''u'''<sub>1</sub>, ..., '''u'''<sub>4</sub> (note that none of them are the zero vector). Since {{Nowrap|φ((0, 0)) {{=}} 0}} by another application of the previous step we have '''u'''<sub>1</sub>, ..., '''u'''<sub>4</sub> as the images of 1-step vectors of ''w''. Since ''w'' is ternary, exactly two of these vectors will be pairwise equal, say '''u'''<sub>''k''</sub> = '''u'''<sub>''l''</sub>. These four "quadrants" intersect in <math>[-m + 1 : m] \times \{0\} \cup \{0\} \times [-n + 1 : n],</math> entailing that '''u'''<sub>''k''</sub> = '''u'''<sub>''l''</sub> is on a coordinate axis (either the '''v'''-coordinate is 0 or the '''w'''-coordinate is 0 but not both). | ||
=== Lemma: If ''n'' > 2 and ''a'' has order > ''n'' in {{nowrap|ℤ/''mn''ℤ}}, then {{nowrap|{0, ''a'', 2''a'', ..., (''n'' - 1)''a''}}} | === Lemma: If ''n'' > 2 and ''a'' has order > ''n'' in {{nowrap|ℤ/''mn''ℤ}}, then {{nowrap|{0, ''a'', 2''a'', ..., (''n'' - 1)''a''}}} meets some window of 2''m'' - 1 adjacent elements at least twice === | ||
Apply the pigeonhole principle: Since ''m'' > 1, we have | |||
ceil(''mn''/(2''m''-1)) | |||
= ceil(''n''/(2 - 1/''m'')) | |||
≤ ceil(2''n''/3) pigeonholes | |||
< ''n'' pigeons. | |||
=== Step 4: The axial step is a MOS substitution slot letter === | === Step 4: The axial step is a MOS substitution slot letter === | ||