Walsh permutation; nimber multiplication

Walsh permutation

Sets of consecutive integers from 0 are closed under nim-multiplication when their cardinalities are Fermat 2-powers 2, 4, 16, 256, 65536... (Sloane'sA001146)
So useful nim-multiplication tables are square matrices of size .
Their rows are -bit Walsh permutations, and the corresponding compression vectors give a matrix.
The columns of this matrix are again Walsh permutations.
Their compression vectors give a square matrix of size , 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 -bit Walsh permutation corresponding to each multiplication table, which is the bitwise XOR of the other ones.
Its compression vector is the bitwise XOR of their compression vectors.


Multiplication tables and compression vectors edit

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 (P0)2 and (P0T)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 edit


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:

 



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