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		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
																		2	3	8	12	5
																		8	12	5	10	11
																		12	4	10	15	13

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	CM	CV				X
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0		0	0	0	0	0
1	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		1	2	4	8	15
2	0	2	3	1	8	10	11	9	12	14	15	13	4	6	7	5		2	3	8	12	5
3	0	3	1	2	12	15	13	14	4	7	5	6	8	11	9	10		3	1	12	4	10
4	0	4	8	12	6	2	14	10	11	15	3	7	13	9	5	1		8	12	5	10	11
5	0	5	10	15	2	7	8	13	3	6	9	12	1	4	11	14		9	14	1	2	4
6	0	6	11	13	14	8	5	3	7	1	12	10	9	15	2	4		10	15	13	6	14
7	0	7	9	14	10	13	3	4	15	8	6	1	5	2	12	11		11	13	9	14	1
8	0	8	12	4	11	3	7	15	13	5	1	9	6	14	10	2		12	4	10	15	13
9	0	9	14	7	15	6	1	8	5	12	11	2	10	3	4	13		13	6	14	7	2
10	0	10	15	5	3	9	12	6	1	11	14	4	2	8	13	7		14	7	2	3	8
11	0	11	13	6	7	12	10	1	9	2	4	15	14	5	3	8		15	5	6	11	7
12	0	12	4	8	13	1	9	5	6	10	2	14	11	7	15	3		4	8	15	5	6
13	0	13	6	11	9	4	15	2	14	3	8	5	7	10	1	12		5	10	11	13	9
14	0	14	7	9	5	11	2	12	10	4	13	3	15	1	8	6		6	11	7	9	3
15	0	15	5	10	1	14	4	11	2	13	7	8	3	12	6	9		7	9	3	1	12

wp(2,3,8,12) and wp(3,1,12,4) appear also in section Bent functions as (P₀)² and (P₀^T)²
and as 10^th and 5^th 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

Matrices

Nim-multiplication table:

0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
0   2   3   1   8  10  11   9  12  14  15  13   4   6   7   5
0   3   1   2  12  15  13  14   4   7   5   6   8  11   9  10
0   4   8  12   6   2  14  10  11  15   3   7  13   9   5   1
0   5  10  15   2   7   8  13   3   6   9  12   1   4  11  14
0   6  11  13  14   8   5   3   7   1  12  10   9  15   2   4
0   7   9  14  10  13   3   4  15   8   6   1   5   2  12  11
0   8  12   4  11   3   7  15  13   5   1   9   6  14  10   2
0   9  14   7  15   6   1   8   5  12  11   2  10   3   4  13
0  10  15   5   3   9  12   6   1  11  14   4   2   8  13   7
0  11  13   6   7  12  10   1   9   2   4  15  14   5   3   8
0  12   4   8  13   1   9   5   6  10   2  14  11   7  15   3
0  13   6  11   9   4  15   2  14   3   8   5   7  10   1  12
0  14   7   9   5  11   2  12  10   4  13   3  15   1   8   6
0  15   5  10   1  14   4  11   2  13   7   8   3  12   6   9

Compression vectors:

 0   0   0   0
 1   2   4   8
 2   3   8  12
 3   1  12   4
 8  12   5  10
 9  14   1   2
10  15  13   6
11  13   9  14
12   4  10  15
13   6  14   7
14   7   2   3
15   5   6  11
 4   8  15   5
 5  10  11  13
 6  11   7   9
 7   9   3   1

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.

Demonstration in Matlab

Two calculations of the 256x256 nim-multiplication table, here called WP:
WP1 is calculated from the compressed matrix B and WP2 with a recursive function calculating all 256*256 nim-products.
It can be seen that there is also an extreme difference in speed.

>> B

B =

     1     2     4     8    16    32    64   128
     2     3     8    12    32    48   128   192
     8    12     5    10   128   192    80   160
    12     4    10    15   192    64   160   240
   192    64   160   240    17    34    68   136
    64   128   240    80    34    51   136   204
   240    80    96   176   136   204    85   170
    80   160   176   208   204    68   170   255

>> %%%%% Calculation of WP1:
>> 
>> tic 
CV = zeros(256,8) ;
for m=1:8
    CV(1:256,m) = cv2wp( B(:,m)' )' ;   % Take the columns of B as compression vectors and turn them into Walsh permutations, which go to the columns of CV.
end
WP1 = zeros(256) ;
for m=2:256
    WP1(m,1:256) = cv2wp( CV(m,:) ) ;   % Take the rows of CV as compression vectors and turn them into Walsh permutations, which go to the rows of WP1.
end
toc
Elapsed time is 0.688750 seconds.
>> 
>> %%%%% Extract of the 256x8 matrix CV:
>> 
>> [ num2str( [0:17]' ) repmat(' ',18,10) num2str( CV(1:18,:) ) ]

ans =

 0            0    0    0    0    0    0    0    0
 1            1    2    4    8   16   32   64  128   % Row 0 of B   (Would be called B(1,:) in Matlab.)
 2            2    3    8   12   32   48  128  192   % Row 1 of B
 3            3    1   12    4   48   16  192   64
 4            8   12    5   10  128  192   80  160   % Row 2 of B
 5            9   14    1    2  144  224   16   32
 6           10   15   13    6  160  240  208   96
 7           11   13    9   14  176  208  144  224
 8           12    4   10   15  192   64  160  240   % Row 3 of B
 9           13    6   14    7  208   96  224  112
10           14    7    2    3  224  112   32   48
11           15    5    6   11  240   80   96  176
12            4    8   15    5   64  128  240   80
13            5   10   11   13   80  160  176  208
14            6   11    7    9   96  176  112  144
15            7    9    3    1  112  144   48   16
16          192   64  160  240   17   34   68  136   % Row 4 of B
17          193   66  164  248    1    2    4    8

>> %%%%% Calculation of WP2:
>> 
>> 
>> tic
WP2 = zeros(256) ;
for m=1:256
    for n=1:256
        WP2(m,n) = nimprod(m-1,n-1) ;
    end
end
toc
Elapsed time is 730.700629 seconds.
>>
>> %%%%% Compare:
>> 
>> isequal(WP1,WP2)   % Are WP1 and WP2 equal?

ans =

     1                % Yes.

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).