cp's OEIS Frontend

In a discussion in the newsgroup de.sci.mathematik, Klaus Nagel (see links) described a bijection P: G -> H between the grid points of two Cartesian grids G{Z X Z} and H{Z X Z} rotated against each other by Pi/4 around the only common point (0,0). This is a variation of the marriage problem asking for a matching in the infinite bipartite graph of the vertices of G U H with small distance d=|P(g)-g| for all points g in G.

Points within the grids are addressed by (i,j) in grid G and by (k,m) in grid H.

The plane is divided into horizontal strips of width cos(Pi/8) = sqrt(sqrt(2)+2)/2, with the x-axis as centerline of strip 0. Grid G is rotated by Pi/8, grid H by -Pi/8.

Assuming proper boundary conditions, there is exactly one grid point of G per grid line i=const and one grid point of grid H per grid line k=const inside each strip.

The intersections of the grid lines i=const from the rotated grid G and of lines k=const from the rotated grid H with the centerline of the strip are determined. The grid points inside the strip are paired such that the distance of the intersection points of lines i=const of grid G and of lines k=const of grid H with the strip centerline is minimized.

This bijection achieves a maximum of all mutual Euclidean distances of all pairs of cos(Pi/8)=0.9238795... (the strip width).

It is conjectured that the least possible maximum distance within pairs can be reduced to sqrt(5)*sin(Pi/8)=0.855706... (A386241), but not further, and that this can be achieved by "local repairs" of the result of the strip bijection, i.e. by reassigning the connections in groups of 4 pairs, one of which being the pair with d>0.8557... and 3 pairs in the vicinity of the violating pair, but potentially addressing points in neighbor strips. The conjecture is supported by extensive numerical results, but an announced proof by Klaus Nagel remained unpublished.

For the current sequence no repair is applied. The first repairs are required beyond i^2+j^2=40. The affected sequence terms for n>=124 are visible in the b-file of A307731.

The results of the matching are shown by enumerating the grid points of grid G according to the sequence pair A305575(n) for i and A305576(n) for j.

After finding the indices of the bijection partners (k,m) in grid H using Klaus Nagel's method, the position L where A305575(L)=k and A305576(L)=m is determined by table lookups, and the unique result is a(n)=L.

The sequence is a permutation of the natural numbers.

Description provided by Klaus Nagel: (Start)

The strip bijection s (A307110) maps a point P[i,j] from a Z X Z grid to Q[u,v] taken from a second grid obtained from the first one by a rotation by Pi/4 around the origin. The coordinates [i,j] and [u,v] refer to the respective grids. If [u,v] also are considered as coordinates of the first grid, the mapping [i,j] --> [u,v] establishes a permutation of the grid points of Z X Z.

Cycles of this permutation are evaluated; the sequence shows the occurring cycle lengths L.

Q[u,v] is located close to P[i,j]. Changing the reference to the other grid causes a rotation by Pi/4. Hence after eight permutation steps any point should return to the vicinity of its starting position. (End)

Therefore the provided visualizations also include graphs showing only every 8th point for cycles with L divisible by 8.

Examples of cycles with lengths > 10^9 are L = 2536863994 for the starting position [1761546, 1379978], L = 5574310746 for start [5207814, 6746677], and L = 6508768664 for start [7983336, 8380845].