A386241 -id:A386241 - cp's OEIS frontend

A307110 Index of matching grid point in the bijection between two infinite quadratic grids with one grid rotated by Pi/4 around the common point (0,0), using an enumeration of the grid points by A305575 and A305576.

0, 1, 6, 3, 8, 2, 11, 4, 9, 5, 15, 7, 19, 14, 10, 16, 17, 18, 12, 20, 13, 26, 27, 28, 25, 21, 22, 23, 24, 38, 31, 40, 33, 42, 35, 44, 29, 30, 51, 32, 53, 34, 55, 36, 49, 57, 58, 59, 60, 62, 39, 64, 41, 66, 43, 68, 37, 46, 47, 48, 45, 50, 63, 52, 65, 54, 67

Offset: 0

Hugo Pfoertner, following a proposal by Rainer Rosenthal, Mar 28 2019

nonn

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.

			The following table shows the first few matched pairs of grid points:
    Grid G     Grid H      Grid H rotated
   n  i  j  a(n) k  m  (k,m) rotated by -Pi/4  distance of matched points
   0  0  0    0  0  0    0.000000  0.000000   0.000000
   1  1  0    1  1  0    0.707107 -0.707107   0.765367
   2  0  1    6 -1  1    0.000000  1.414214   0.414214
   3 -1  0    3 -1  0   -0.707107  0.707107   0.765367
   4  0 -1    8  1 -1    0.000000 -1.414214   0.414214
   5  1  1    2  0  1    0.707107  0.707107   0.414214
   6 -1  1   11 -2  0   -1.414214  1.414214   0.585786
   7 -1 -1    4  0 -1   -0.707107 -0.707107   0.414214
   8  1 -1    9  2  0    1.414214 -1.414214   0.585786
   9  2  0    5  1  1    1.414214  0.000000   0.585786
  10  0  2   15 -1  2    0.707107  2.121320   0.717439
  11 -2  0    7 -1 -1   -1.414214  0.000000   0.585786
  12  0 -2   19  1 -2   -0.707107 -2.121320   0.717439
  13  2  1   14  1  2    2.121320  0.707107   0.317025

Hugo Pfoertner and Rainer Rosenthal, Table of n, a(n) for n = 0..10000
H. Carstens, W. Deuber, W. Thumser, and E. Koppenrade, Geometrical Bijections in Discrete Lattices. Combinatorics, Probability and Computing, 8(1-2), 109-129, 1999.
Klaus Nagel, Zwei Gitter, thread in newsgroup de.sci.mathematik, description of bijection (in German), Jan 7 2007.
Klaus Nagel, Zwei Gitter, thread in newsgroup de.sci.mathematik, modification of strip location (in German), Jan 14 2007.
Hugo Pfoertner, Illustration of strip bijection, (2019).
Rainer Rosenthal, Illustrating examples a(0) ... a(29), Nov 29 2023.

Cf. A144981, A305575, A305576, A307731, A362955, A362956, A363760, A367150, A386241.

/* It is assumed that the files a305575 and a305576 contain the second column of the corresponding b-files */
a305575=readvec(a305575); a305576=readvec(a305576);
p(i,j)={my(C=cos(Pi/8),S=sin(Pi/8),T=S/C,gx=i*C-j*S,gy=i*S+j*C,k,xm,ym,v=[0,0]);
k=round(gy/C); ym=C*k; xm=gx+(gy-ym)*T;
  v[1]=round((xm-ym*T)*C);  v[2]=round((ym+v[1]*S)/C);  v}
findpos(v)={for(k=1,#a305575,if(v[1]==a305575[k]&&v[2]==a305576[k],return(k-1)))}
for(n=1,67,print1(findpos(p(a305575[n],a305576[n])),", "))

A307731 Results of strip bijection as described in A307110 with additional application of local repairs to reduce the maximum wobbling distance S from S1=cos(Pi/8) to S2=sqrt(5)*sin(Pi/8).

Original entry on oeis.org

Offset: 0

Hugo Pfoertner, Apr 25 2019

nonn

The terms visible in the data section are identical with those of A307110. The first difference occurs at a(124)=141, A307110(124)=125.
The wobbling distance S is the mutual Euclidean distance of the pairs matched by a bijection.
.
  - - - G - -\- - - - - - / - G - - - - -\- - - - - G -/- - - - - - - - - G
        |  +   \       /      |             \      +|/                    |
        |      + \   /        |               \   + |                     |
        |          H          |                 H   |                     |
        |       /    \        |               /   \ |                     |
        |     /        \      .     .   .   /       |\                    |
        |  /           . \    |           /  .      |  \                 /|
        |/                 \  |        /        .   |     \            /  |
       /|           .        \|      /            . |        \       /    |
    /   |                     |\   /               .|          \   /      |
  H +   |        .            | +H # # # #          .            H + +    |
  - \ + G - - - - - - - - - - G+ -\- - - - # # # # #G.- - - - - - -\- -+ +G
      \ |       .            #| \   \              +| .        /     \    |
        \                   # |  D    \            +|        /          \ |
        | \    .          #   |   \     \          +|      /              \
        |   \   <--------r=S1------C      \       + |  ./                 |
        |     \       #       |     B        \    + | /                   |
        |       .   #         |      B          \ + /                     |
        |        .H+          |       B           H |.                    |
        |       /   \++       |        B        /  #.                     |
        |     /   .   \++     |        B      /    #| \                   |
        |   /       .   \+++  |         B   /     . #   \                 |
  - - - G / - - - - - . - \ -+G - - - - -B/ - - .  +G - - \ - - - - - - - G
      + /               .   \ |#        / B    +E+. | .     \           + /
     +/ |                     . #     /.  +M+       |       . \      + /  |
   +/   |                     | \#  / +E+   b       |          .\   +/    |
  H     |                     |   H+ .       b      |            .H       |
    \   |                     | /  .\         b     |           /  .\     |
      \ |                     /   .   \        b    |         /     . \   |
        \                   / |  .       \      b   |      /            \ |
        | \               /   | .          \     b  |   /             .   \
        |   \           /     |.             \    b | /                   |
        |     \       /       |.                \  c--------r=S1------>.  |
  - - - G+++++- \ - / - - - - G.- - - - - - - - - HdG - - - - - - - - -.- G
        |     ++++H           +.                /   \                  .  |
        |       /   \         |+              /     | \                   |
        |    /         \      |+.           /       |   \             .   |
        |  /             \    | +         /         |     \          .    /
        |/                  \ | + .     /           |       \       .   / |
       /                      \  + .  /             |          \   .  /   |
    /   |                     | \ + .               |             . /     |
  H     |                     |   H   .             |           . H       |
    \   |                     | /   \       .       |       .   /    +    |
      \ |                     /        \            .         /         + |
  - - - G - - - - - - - - - / G - - - - -\- - - - - G - - - / - - - - - - G
.
The ASCII graphics above shows the situation after the application of the strip bijection, as it is described in A307110, for a position in the grids containing a "long" junction exceeding the length S2. The linked graphics file "Construction of repair" shows a similar configuration, but without labels.
All junctions resulting from the strip bijection are marked by plus signs. The long junction is marked by embedded letters "E". There are 6 possible orientations of E-junctions (called E for short), but the method for their elimination is identical for all cases.
The target of the method is to achieve a local reconnecting, which replaces 4 junctions by circularly shifted new junctions. To determine the affected grid points, the following steps are performed:
From the midpoint (marked by M in the figure) of E construct a bisecting line Bb perpendicular to E. Draw two circles, one on each side of E with centers on B and b at distance S1 from M. E is a tangent at M of these circles with radius r = S1. The two circles are marked by dots ".." in the figure.
For the two circle centers C and c determine the distances D and d of the respective closest grid points in lattice G. The position (c) of the circle center, for which this minimum distance is smaller, indicates on which side of E no reconnecting is required. A circle with radius S1 around c contains only one grid point of G and one of H. All other grid points of both lattices lie outside of this circle.
The side of E with the larger distance between circle center and closest grid point is where the circular shift of junctions is to be performed. The circle around C with radius r = S1 contains 3 grid points of lattice G and 3 grid points of lattice H.
After having found c, it is possible to replace the geometric determination of the 3 grid point pairs on the opposite side of E by a lookup in a table of differences between the coordinates of M and c rounded to nearest integers, leading to a unique identification of the 6 occurring cases. The function "repair" in the PARI program implements this selection.
The 4 new junctions are marked by "###" in the figure. They replace the 4 previous "+++" junctions, including the long junction E. The maximum of their lengths does not exceed S2, approaching S2 for length of E approaching S1. The limiting case for the 4 rearranged junctions are two of length S2 and two of length sin(Pi/8) = 0.38268...
The described repair is applied to all occurrences of bijection distances exceeding S2 within the overlay of the two lattices. Numerical experiments with random points on square lattices of huge size show that approximately 0.956 % (roughly 1/105) of the grid points lead to a bijection distance S > S2 after the application of the strip bijection. No counterexample for the validity of the method is known, but a formal proof is missing.
In the ring-wise one-dimensional mapping of the bijection as given by A307110, the first affected position is n = 124. The table in the example section shows the corresponding changes for this earliest repair together with the listing of another repair with different orientation of E.
All affected index positions have to be exchanged in the one-dimensional list. Due to the occurrence frequency of E-junctions the current sequence is expected to differ from A307110 for roughly 4% of the terms.
The PARI program provided as external file is self-contained, including the code for generation of the rings used for 1d-mapping, A305575 and A305576, and the code for the strip bijection of A307110. To generate a b-file of 10000 terms, the corresponding code lines at the end of the program have to be activated.

			The table shows the first re-matched pairs of grid points together with the result of the unmodified strip bijection:
    Grid G          Grid H             Grid H rotated
   n     i    j    a(n)   k    m   (k,m) rotated by -Pi/4  distance of
                                                           matched points
  124   -6    2    141   -6   -3    -6.363961   2.121320   0.383648
  140   -6    3    125   -6   -2    -5.656854   2.828427   0.383649
  180   -7    3    173   -7   -2    -6.363961   3.535534   0.831470 < S2
  172   -7    2    181   -7   -3    -7.071068   2.828427   0.831470 < S2
  ...
  266   -6    7    256   -9    1    -5.656854   7.071068   0.350428
  309   -6    8    320  -10    1    -6.363961   7.778174   0.426232
  279   -5    8    328  -10    2    -5.656854   8.485281   0.816673 < S2
  235   -5    7    268   -9    2    -4.949747   7.778174   0.779795 < S2
compared to (unmodified):                                        S2=0.855706..
                A307110(n)
  124   -6    2    125   -6   -2    -5.656854   2.828427   0.896683 > S2
  140   -6    3    173   -7   -2    -6.363961   3.535534   0.647506
  180   -7    3    181   -7   -3    -7.071068   2.828427   0.185709
  172   -7    2    141   -6   -3    -6.363961   2.121320   0.647506
  ...
  266   -6    7    320  -10    1    -6.363961   7.778174   0.859083 > S2
  309   -6    8    328  -10    2    -5.656854   8.485281   0.594346
  279   -5    8    268   -9    2    -4.949747   7.778174   0.227446
  235   -5    7    256   -9    1    -5.656854   7.071068   0.660688

Hugo Pfoertner, Table of n, a(n) for n = 0..10000
Hugo Pfoertner, Construction of repair.
Hugo Pfoertner, Repair of strip bijection.
Hugo Pfoertner, Illustration of repair locations, 10000 grid points. Zoom in to see details.
Hugo Pfoertner, PARI program for A307731.

Cf. A144981, A305575, A305576, A307110, A367150, A386241.

PARI
```
\\ See Pfoertner link.
```

cp's OEIS Frontend

A307110 Index of matching grid point in the bijection between two infinite quadratic grids with one grid rotated by Pi/4 around the common point (0,0), using an enumeration of the grid points by A305575 and A305576.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI