# Walsh permutation; nimber multiplication

Sets of consecutive integers from 0 are closed under nim-multiplication when their cardinalities are Fermat 2-powers 2, 4, 16, 256, 65536... ( A001146) So useful nim-multiplication tables are square matrices of size $2^{2^{n}}$. Their rows are $2^{n}$-bit Walsh permutations, and the corresponding compression vectors give a $2^{2^{n}}\times 2^{n}$ matrix. The $2^{n}$ columns of this matrix are again Walsh permutations. Their compression vectors give a square matrix of size $2^{n}$, which is thus a compression of the multiplication table. (Of course there is no Walsh permutation wp(zeros), but here it makes sense to write it that way.) There is another $2^{n}$-bit Walsh permutation corresponding to each multiplication table, which is the bitwise XOR of the $2^{n}$ other ones. Its compression vector is the bitwise XOR of their compression vectors.

## Multiplication tables and compression vectors

| | | | | 1 |
| | 0 | 1 | CM | CV |
| 0 | 0 | 0 | | 0 |
| 1 | 0 | 1 | | 1 |
| | | | | | | 1 | 2 | 3 |
| | | | | | | 2 | 3 | 1 |
| | 0 | 1 | 2 | 3 | CM | CV | CV | X |
| 0 | 0 | 0 | 0 | 0 | | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | | 1 | 2 | 3 |
| 2 | 0 | 2 | 3 | 1 | | 2 | 3 | 1 |
| 3 | 0 | 3 | 1 | 2 | | 3 | 1 | 2 |
| 1 2 4 8 15 238125 81251011 124101513 0123456789101112131415 CM CV X 0  0000000000000000 00000 1 0123456789101112131415 124815 2 0231810119121415134675 238125 3 0312121513144756811910 3112410 4 0481262141011153713951 81251011 5 0510152781336912141114 914124 6 0611131485371121091524 101513614 7 0791410133415861521211 11139141 8 0812411371513519614102 124101513 9 0914715618512112103413 1361472 10 0101553912611114428137 147238 11 0111367121019241514538 1556117 12 0124813195610214117153 481556 13 0136119415214385710112 51011139 14 0147951121210413315186 611793 15 0155101144112137831269 793112 wp(2,3,8,12) and wp(3,1,12,4) appear also in section Bent functions as (P$_0$)$^2$ and (P$_0$$^T$)$^2$ and as 10th and 5th power of wp(15, 5,11,13). Powers | Multiplication table for nimbers from 0 to 15 The dual matrix shows binary Walsh matrices permuted by wp(1,2,8,12) etc. Patterns |
In the table above it can be seen that all rows (in the nim-multiplication table and in the table of compression vectors) are bit-XORs of 2-power rows. (So both columns and rows of the beige square matrix appear as compression vectors.)
Further it can be seen that the nim-products of 2-powers are related to the compression vectors on the right. (Read the compression matrices on the right row by row instead of column by column.) So in the end all the information in the table of nim-products is compressed in the table of nim-products of 2-powers.
The multiplication table of the nimbers 0..255 is here. The 8 elements of the dual matrix are here.

## Infinite arrays

Matrices :
| 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | 8192 | 16384 | 32768 |
| 2 | 3 | 8 | 12 | 32 | 48 | 128 | 192 | 512 | 768 | 2048 | 3072 | 8192 | 12288 | 32768 | 49152 |
| 4 | 8 | 6 | 11 | 64 | 128 | 96 | 176 | 1024 | 2048 | 1536 | 2816 | 16384 | 32768 | 24576 | 45056 |
| 8 | 12 | 11 | 13 | 128 | 192 | 176 | 208 | 2048 | 3072 | 2816 | 3328 | 32768 | 49152 | 45056 | 53248 |
| 16 | 32 | 64 | 128 | 24 | 44 | 75 | 141 | 4096 | 8192 | 16384 | 32768 | 6144 | 11264 | 19200 | 36096 |
| 32 | 48 | 128 | 192 | 44 | 52 | 141 | 198 | 8192 | 12288 | 32768 | 49152 | 11264 | 13312 | 36096 | 50688 |
| 64 | 128 | 96 | 176 | 75 | 141 | 103 | 185 | 16384 | 32768 | 24576 | 45056 | 19200 | 36096 | 26368 | 47360 |
| 128 | 192 | 176 | 208 | 141 | 198 | 185 | 222 | 32768 | 49152 | 45056 | 53248 | 36096 | 50688 | 47360 | 56832 |
| 256 | 512 | 1024 | 2048 | 4096 | 8192 | 16384 | 32768 | 384 | 704 | 1200 | 2256 | 4237 | 8390 | 16569 | 32990 |
| 512 | 768 | 2048 | 3072 | 8192 | 12288 | 32768 | 49152 | 704 | 832 | 2256 | 3168 | 8390 | 12363 | 32990 | 49255 |
| 1024 | 2048 | 1536 | 2816 | 16384 | 32768 | 24576 | 45056 | 1200 | 2256 | 1648 | 2960 | 16569 | 32990 | 24703 | 45205 |
| 2048 | 3072 | 2816 | 3328 | 32768 | 49152 | 45056 | 53248 | 2256 | 3168 | 2960 | 3552 | 32990 | 49255 | 45205 | 53482 |
| 4096 | 8192 | 16384 | 32768 | 6144 | 11264 | 19200 | 36096 | 4237 | 8390 | 16569 | 32990 | 6237 | 11430 | 19241 | 36158 |
| 8192 | 12288 | 32768 | 49152 | 11264 | 13312 | 36096 | 50688 | 8390 | 12363 | 32990 | 49255 | 11430 | 13563 | 36158 | 50711 |
| 16384 | 32768 | 24576 | 45056 | 19200 | 36096 | 26368 | 47360 | 16569 | 32990 | 24703 | 45205 | 19241 | 36158 | 26511 | 47557 |
| 32768 | 49152 | 45056 | 53248 | 36096 | 50688 | 47360 | 56832 | 32990 | 49255 | 45205 | 53482 | 36158 | 50711 | 47557 | 56906 |
| The rows of Matrix A are treated as compression vectors. They are transformed into the corresponding compression matrices. Than these matrices are transposed. The compression vectors corresponding to the transposed matrices are the rows of Matrix B. | Matlab code: B=zeros(16); for m=1:16 B(m,1:16) = cm2cv( cv2cm( A(m,1:16) )' ) ; end |
| 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | 8192 | 16384 | 32768 |
| 2 | 3 | 8 | 12 | 32 | 48 | 128 | 192 | 512 | 768 | 2048 | 3072 | 8192 | 12288 | 32768 | 49152 |
| 8 | 12 | 5 | 10 | 128 | 192 | 80 | 160 | 2048 | 3072 | 1280 | 2560 | 32768 | 49152 | 20480 | 40960 |
| 12 | 4 | 10 | 15 | 192 | 64 | 160 | 240 | 3072 | 1024 | 2560 | 3840 | 49152 | 16384 | 40960 | 61440 |
| 192 | 64 | 160 | 240 | 17 | 34 | 68 | 136 | 49152 | 16384 | 40960 | 61440 | 4352 | 8704 | 17408 | 34816 |
| 64 | 128 | 240 | 80 | 34 | 51 | 136 | 204 | 16384 | 32768 | 61440 | 20480 | 8704 | 13056 | 34816 | 52224 |
| 240 | 80 | 96 | 176 | 136 | 204 | 85 | 170 | 61440 | 20480 | 24576 | 45056 | 34816 | 52224 | 21760 | 43520 |
| 80 | 160 | 176 | 208 | 204 | 68 | 170 | 255 | 20480 | 40960 | 45056 | 53248 | 52224 | 17408 | 43520 | 65280 |
| 20480 | 40960 | 45056 | 53248 | 52224 | 17408 | 43520 | 65280 | 257 | 514 | 1028 | 2056 | 4112 | 8224 | 16448 | 32896 |
| 40960 | 61440 | 53248 | 24576 | 17408 | 34816 | 65280 | 21760 | 514 | 771 | 2056 | 3084 | 8224 | 12336 | 32896 | 49344 |
| 53248 | 24576 | 57344 | 28672 | 65280 | 21760 | 26112 | 47872 | 2056 | 3084 | 1285 | 2570 | 32896 | 49344 | 20560 | 41120 |
| 24576 | 45056 | 28672 | 36864 | 21760 | 43520 | 47872 | 56576 | 3084 | 1028 | 2570 | 3855 | 49344 | 16448 | 41120 | 61680 |
| 21760 | 43520 | 47872 | 56576 | 39936 | 58368 | 6656 | 12032 | 49344 | 16448 | 41120 | 61680 | 4369 | 8738 | 17476 | 34952 |
| 43520 | 65280 | 56576 | 26112 | 58368 | 30720 | 12032 | 13568 | 16448 | 32896 | 61680 | 20560 | 8738 | 13107 | 34952 | 52428 |
| 56576 | 26112 | 60928 | 30464 | 12032 | 13568 | 34304 | 51968 | 61680 | 20560 | 24672 | 45232 | 34952 | 52428 | 21845 | 43690 |
| 26112 | 47872 | 30464 | 39168 | 13568 | 6656 | 51968 | 19712 | 20560 | 41120 | 45232 | 53456 | 52428 | 17476 | 43690 | 65535 |
* 1
* 3
* 1
* 15
* 5
* 11
* 13
* 255
* 85
* 187
* 221
* 47
* 53
* 203
* 77
* 65535
* 21845
* 48059
* 56797
* 12079
* 13621
* 52171
* 19789
* 45823
* 54101
* 60603
* 29917
* 64303
* 23861
* 48843
* 55117
Here is a closer look at the nim-products of the first 16 powers of 2 ( A223541). It shows the binary representation of the entries and the dual matrix where bits with the same position are shown together:
Representation as binary tensors :
Although it is hard to see, each tensor can be produced from the other one by rotation. :
The compressed multiplication table of the first 256 nimbers ( A223537):
Read by rows these are the compression vectors of rows 1,2,4,8,...,128. The diagonal is  A001317 (Sierpinski triangle rows read like binary numbers).