1 | initial version |

The question is not well defined.

There are some standard guesses on the road, that make the word "linear" get a sense. This should come in the question. However, since there was a chance to "guess the linearity" in the more complicated example of the permutation mapping (0,1,...,255) to (0,29,142,...) i'll post the code that recovers "linearly" the map.

(Note: There is also a first guess that 256 was a typo, so that we are working over an algebraic structure with $256$ instead of $257$ elements. Both numbers are prime powers and there are chances in both cases to give a sense to the word "linear". There will be further guesses. I am not complaining, but if this is not the answer to the question, this is because the question is interpretable.)

The code in the sequel will do the following:

Let $F$ be the field with two elements. In sage it is `GF(2)`

. Let $V=F^{\times 8}$ be the canonical vector space of dimension $8$ over $F$, its elements are column vectors with eight components, the zero of $F$ and the one of $F$. We will identify the *set* ${0,1,2,\dots,255}$ with the underlying *set* of $V$ (built out of $V$ by the forgetful functor) in the following way:

Take an *integer* number in the first set, take its coefficients in base two, they are $0$ or $1$ (in $\mathbb Z$), fill in the data to a vector with eight components, map then on components $0_{\mathbb Z}\to 0_F$ and $1_{\mathbb Z}\to 1_F$.

The sage code for this, starting with $99\in\mathbb Z$ would be:

```
sage: 99.digits( base=2 )
[1, 1, 0, 0, 0, 1, 1]
sage: 99.digits( base=2, padto=8 ) # even better for us
[1, 1, 0, 0, 0, 1, 1, 0]
sage: vector( GF(2), 99.digits( base=2, padto=8 ) ) # element in vector space
(1, 1, 0, 0, 0, 1, 1, 0)
```

Conversely, from the above vector we have to lift the components from `GF(2)`

to the integers, applying `ZZ`

on the zero or one of the `GF(2)`

, then to use the "right two-powers" to get the number between $0$ and $255$. The function `encode`

will do this in the sequel, we have to write it.

Note that this bijection (at sets level) is not canonical, it is our choice / our guess, the question has to make it specific.

OK, the code now, half of it is copy-pasted:

```
L = (0, 29, 142, 147, 199, 218, 73, 84, 227, 254, 109, 112, 36, 57, 170, 183, 113, 108, 255, 226, 182, 171, 56, 37, 146, 143, 28, 1, 85, 72, 219, 198, 184, 165, 54, 43, 127, 98, 241, 236, 91, 70, 213, 200, 156, 129, 18, 15, 201, 212, 71, 90, 14, 19, 128, 157, 42, 55, 164, 185, 237, 240, 99, 126, 220, 193, 82, 79, 27, 6, 149, 136, 63, 34, 177, 172, 248, 229, 118, 107, 173, 176, 35, 62, 106, 119, 228, 249, 78, 83, 192, 221, 137, 148, 7, 26, 100, 121, 234, 247, 163, 190, 45, 48, 135, 154, 9, 20, 64, 93, 206, 211, 21, 8, 155, 134, 210, 207, 92, 65, 246, 235, 120, 101, 49, 44, 191, 162, 238, 243, 96, 125, 41, 52, 167, 186, 13, 16, 131, 158, 202, 215, 68, 89, 159, 130, 17, 12, 88, 69, 214, 203, 124, 97, 242, 239, 187, 166, 53, 40, 86, 75, 216, 197, 145, 140, 31, 2, 181, 168, 59, 38, 114, 111, 252, 225, 39, 58, 169, 180, 224, 253, 110, 115, 196, 217, 74, 87, 3, 30, 141, 144, 50, 47, 188, 161, 245, 232, 123, 102, 209, 204, 95, 66, 22, 11, 152, 133, 67, 94, 205, 208, 132, 153, 10, 23, 160, 189, 46, 51, 103, 122, 233, 244, 138, 151, 4, 25, 77, 80, 195, 222, 105, 116, 231, 250, 174, 179, 32, 61, 251, 230, 117, 104, 60, 33, 178, 175, 24, 5, 150, 139, 223, 194, 81, 76)
F = GF(2)
A = matrix( F, 8,8 )
for k in [0..7]:
A[ : , k ] = column_matrix( F, L[ 2**k ].digits( base=2, padto=8 ) )
print "The matrix A is:"
print A
def encode( c ):
return sum( [ 2^k * ZZ( c[k] )
for k in range(len(c)) ] )
LL = [ encode( A * vector( F, ZZ(j).digits( base=2, padto=8 ) ) )
for j in range(256) ]
print "Is the constructed list recovering L? %s" % ( LL == list(L) )
```

Running it we get:

```
The matrix A is:
[1 0 1 1 1 0 0 0]
[0 1 1 1 0 0 0 1]
[1 1 1 0 0 0 1 1]
[1 1 0 0 0 1 1 1]
[1 0 0 0 1 1 1 0]
[0 0 0 1 1 1 0 1]
[0 0 1 1 1 0 1 1]
[0 1 1 1 0 1 1 1]
Is the constructed list recovering L? True
```

So in a very conventional way, up to a guessed bijection, the permutation is induced by multiplication with the

Note:

```
sage: A.det()
1
sage: A.multiplicative_order()
85
```

so we expect that the given permutation splits into some cycles of length $85$. (And the $0$ remains $0$.) Indeed, the corresponding permutation can be easily associated, this time using the world of permutations, which want integers $1,2,\dots, 256$, and its order and cycles can be required. Here is the small dialog:

```
sage: S = SymmetricGroup( 256 )
sage: s = S( [ k+1 for k in L ] )
sage: s.order()
85
sage: for c in s.cycles():
....: print "Found cycle of order %s" % c.order()
....:
Found cycle of order 85
Found cycle of order 85
Found cycle of order 85
```

(A last check: $1+85+85+85=256$. The $1$-cycle corresponds to the zero.)

Note: I tried also to even realize the "linear map" over a ring (or field for optimists), but the natural identification of the above vector space with the polynomial ring $F[X]$ modulo some polynomial could not be performed. The modulus polynomial $f$ should be then recovered from $29=L[1]$ and $72=L[L[1]]$. So that $f$ decodes $29$ and $f^2$ decodes $72$. But then $f^3$... For instance:

```
sage: R.<X> = PolynomialRing( GF(2) )
sage: f = R( 29.digits( base=2 ) )
sage: ff = R( 72.digits( base=2 ) )
sage: fff = R( 63.digits( base=2 ) )
sage: (f^2 - ff).factor()
(X + 1) * (X^7 + X^6 + X^5 + X^4 + X^2 + X + 1)
sage: (f^3 - fff).factor()
X * (X + 1) * (X^5 + X^3 + 1) * (X^5 + X^3 + X^2 + X + 1)
```

So it seems i am missing the final, ultimative guess.

2 | No.2 Revision |

The question is not well defined.

There are some standard guesses on the road, that make the word "linear" get a sense. This should come in the question. However, since there was a chance to "guess the linearity" in the more complicated example of the permutation mapping (0,1,...,255) to (0,29,142,...) i'll post the code that recovers "linearly" the map.

(Note: There is also a first guess that 256 was a typo, so that we are working over an algebraic structure with $256$ instead of $257$ elements. Both numbers are prime powers and there are chances in both cases to give a sense to the word "linear". There will be further guesses. I am not complaining, but if this is not the answer to the question, this is because the question is interpretable.)

The code in the sequel will do the following:

Let $F$ be the field with two elements. In sage it is `GF(2)`

. Let $V=F^{\times 8}$ be the canonical vector space of dimension $8$ over $F$, its elements are column vectors with eight components, the zero of $F$ and the one of $F$. We will identify the *set* ${0,1,2,\dots,255}$ with the underlying *set* of $V$ (built out of $V$ by the forgetful functor) in the following way:

Take an *integer* number in the first set, take its coefficients in base two, they are $0$ or $1$ (in $\mathbb Z$), fill in the data to a vector with eight components, map then on components $0_{\mathbb Z}\to 0_F$ and $1_{\mathbb Z}\to 1_F$.

The sage code for this, starting with $99\in\mathbb Z$ would be:

```
sage: 99.digits( base=2 )
[1, 1, 0, 0, 0, 1, 1]
sage: 99.digits( base=2, padto=8 ) # even better for us
[1, 1, 0, 0, 0, 1, 1, 0]
sage: vector( GF(2), 99.digits( base=2, padto=8 ) ) # element in vector space
(1, 1, 0, 0, 0, 1, 1, 0)
```

Conversely, from the above vector we have to lift the components from `GF(2)`

to the integers, applying `ZZ`

on the zero or one of the `GF(2)`

, then to use the "right two-powers" to get the number between $0$ and $255$. The function `encode`

will do this in the sequel, we have to write it.

Note that this bijection (at sets level) is not canonical, it is our choice / our guess, the question has to make it specific.

OK, the code now, half of it is copy-pasted:

```
L = (0, 29, 142, 147, 199, 218, 73, 84, 227, 254, 109, 112, 36, 57, 170, 183, 113, 108, 255, 226, 182, 171, 56, 37, 146, 143, 28, 1, 85, 72, 219, 198, 184, 165, 54, 43, 127, 98, 241, 236, 91, 70, 213, 200, 156, 129, 18, 15, 201, 212, 71, 90, 14, 19, 128, 157, 42, 55, 164, 185, 237, 240, 99, 126, 220, 193, 82, 79, 27, 6, 149, 136, 63, 34, 177, 172, 248, 229, 118, 107, 173, 176, 35, 62, 106, 119, 228, 249, 78, 83, 192, 221, 137, 148, 7, 26, 100, 121, 234, 247, 163, 190, 45, 48, 135, 154, 9, 20, 64, 93, 206, 211, 21, 8, 155, 134, 210, 207, 92, 65, 246, 235, 120, 101, 49, 44, 191, 162, 238, 243, 96, 125, 41, 52, 167, 186, 13, 16, 131, 158, 202, 215, 68, 89, 159, 130, 17, 12, 88, 69, 214, 203, 124, 97, 242, 239, 187, 166, 53, 40, 86, 75, 216, 197, 145, 140, 31, 2, 181, 168, 59, 38, 114, 111, 252, 225, 39, 58, 169, 180, 224, 253, 110, 115, 196, 217, 74, 87, 3, 30, 141, 144, 50, 47, 188, 161, 245, 232, 123, 102, 209, 204, 95, 66, 22, 11, 152, 133, 67, 94, 205, 208, 132, 153, 10, 23, 160, 189, 46, 51, 103, 122, 233, 244, 138, 151, 4, 25, 77, 80, 195, 222, 105, 116, 231, 250, 174, 179, 32, 61, 251, 230, 117, 104, 60, 33, 178, 175, 24, 5, 150, 139, 223, 194, 81, 76)
F = GF(2)
A = matrix( F, 8,8 )
for k in [0..7]:
A[ : , k ] = column_matrix( F, L[ 2**k ].digits( base=2, padto=8 ) )
print "The matrix A is:"
print A
def encode( c ):
return sum( [ 2^k * ZZ( c[k] )
for k in range(len(c)) ] )
LL = [ encode( A * vector( F, ZZ(j).digits( base=2, padto=8 ) ) )
for j in range(256) ]
print "Is the constructed list recovering L? %s" % ( LL == list(L) )
```

Running it we get:

```
The matrix A is:
[1 0 1 1 1 0 0 0]
[0 1 1 1 0 0 0 1]
[1 1 1 0 0 0 1 1]
[1 1 0 0 0 1 1 1]
[1 0 0 0 1 1 1 0]
[0 0 0 1 1 1 0 1]
[0 0 1 1 1 0 1 1]
[0 1 1 1 0 1 1 1]
Is the constructed list recovering L? True
```

So in a very conventional way, up to a guessed bijection, the permutation is induced by multiplication with the (symmetric!) matrix $A$ above.

Note:

```
sage: A.det()
1
sage: A.multiplicative_order()
85
```

so we expect that the given permutation splits into some cycles of length $85$. (And the $0$ remains $0$.) Indeed, the corresponding permutation can be easily associated, this time using the world of permutations, which want integers $1,2,\dots, 256$, and its order and cycles can be required. Here is the small dialog:

```
sage: S = SymmetricGroup( 256 )
sage: s = S( [ k+1 for k in L ] )
sage: s.order()
85
sage: for c in s.cycles():
....: print "Found cycle of order %s" % c.order()
....:
Found cycle of order 85
Found cycle of order 85
Found cycle of order 85
```

(A last check: $1+85+85+85=256$. The $1$-cycle corresponds to the zero.)

Note: I tried also to even realize the "linear map" over a ring (or field for optimists), but the natural identification of the above vector space with the polynomial ring $F[X]$ modulo some polynomial could not be performed. The modulus polynomial $f$ should be then recovered from $29=L[1]$ and $72=L[L[1]]$. So that $f$ decodes $29$ and $f^2$ decodes $72$. But then $f^3$... For instance:

```
sage: R.<X> = PolynomialRing( GF(2) )
sage: f = R( 29.digits( base=2 ) )
sage: ff = R( 72.digits( base=2 ) )
sage: fff = R( 63.digits( base=2 ) )
sage: (f^2 - ff).factor()
(X + 1) * (X^7 + X^6 + X^5 + X^4 + X^2 + X + 1)
sage: (f^3 - fff).factor()
X * (X + 1) * (X^5 + X^3 + 1) * (X^5 + X^3 + X^2 + X + 1)
```

So it seems i am missing the final, ultimative guess.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.