Let us restrict ourselves to odd magic squares constructed using the Uniform Step Method of Lehmer (See [Apostol51] for the construction technique).
A magic square constructed using Lehmer’s Uniform Step Method as follows:
The $n^2$ cells of the square are denoted by the coordinates $(A,B)$ with $A$ being the number of the column counting from the left and $B$ the number of the row counting from the bottom.
The cell $(A_x,B_x)$ into which the number $x$ is entered is given by $$\begin{align} A_x≡p+α(x-1)+a\left[\frac{x-1}{n}\right] \pmod{n}\\ B_x≡q+β(x-1)+b\left[\frac{x-1}{n}\right] \pmod{n} \end{align} \tag{1}$$ where $(p,q)$ is the cell into which the number $1$ is entered, $(α,β)$ is the step used in proceeding from one cell to another and $(a,b)$ is the break-step that must be used when an occupied cell is arrived at and $[k]$ denotes the greatest integer contained in $k$.
Definition. Consider the $\Delta_{\delta}(x)$ the $\delta \times \delta$ submatrix of the magic square with $\delta$ odd and the element $x$ in its center. i.e.,
$$ \Delta_{\delta}(x) = \begin{matrix} a_{i-[\delta/2],j-[\delta/2]} & \cdots & a_{i-[\delta/2],j} & \cdots & a_{i-[\delta/2],j+[\delta/2]} \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ a_{i,j-[\delta/2]} & \cdots & a_{i,j}=x & \cdots & a_{i,j+[\delta/2]} \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ a_{i+[\delta/2],j-[\delta/2]} & \cdots & a_{i+[\delta/2],j} & \cdots & a_{i+[\delta/2],j+[\delta/2]} \end{matrix} $$
The arithmetic over the indices is taken modulo $n$ so that the submatrix $\Delta_{\delta}(x)$ is defined for all entries of the magic square, including the entries on the edges.
Define $G_{\delta}(x)$, the $\delta \times \delta$ GCD matrix of $x$ having $(i,j)$-th entry $g_{i,j} = \gcd(a_{i,j}, x)$ where $a_{i,j}$ is the $(i,j)$-th entry of $\Delta_{\delta}(x)$.
Consider the following $31 \times 31$ magic square.
$$ \begin{smallmatrix} 498 & 531 & 564 & 597 & 630 & 663 & 696 & 729 & 762 & 795 & 828 & 861 & 894 & 927 & 960 & 1 & 34 & 67 & 100 & 133 & 166 & 199 & 232 & 265 & 298 & 331 & 364 & 397 & 430 & 463 & 496 \newline 530 & 563 & 596 & 629 & 662 & 695 & 728 & 761 & 794 & 827 & 860 & 893 & 926 & \bf{959} & 31 & 33 & 66 & 99 & 132 & 165 & 198 & 231 & 264 & 297 & 330 & 363 & 396 & 429 & 462 & 495 & 497 \newline 562 & 595 & 628 & 661 & 694 & 727 & 760 & 793 & 826 & 859 & 892 & 925 & 958 & 30 & 32 & 65 & 98 & 131 & 164 & 197 & 230 & 263 & 296 & 329 & 362 & 395 & 428 & 461 & 494 & 527 & 529 \newline 594 & 627 & 660 & 693 & 726 & 759 & 792 & 825 & 858 & 891 & 924 & 957 & 29 & 62 & 64 & 97 & 130 & 163 & 196 & 229 & 262 & 295 & 328 & 361 & 394 & 427 & 460 & 493 & 526 & 528 & 561 \newline 626 & 659 & 692 & 725 & 758 & 791 & 824 & 857 & 890 & 923 & 956 & 28 & 61 & 63 & 96 & 129 & 162 & 195 & 228 & 261 & 294 & 327 & 360 & 393 & 426 & 459 & 492 & 525 & 558 & 560 & 593 \newline 658 & 691 & 724 & 757 & 790 & 823 & 856 & 889 & 922 & 955 & 27 & 60 & 93 & 95 & 128 & 161 & 194 & 227 & 260 & 293 & 326 & 359 & 392 & 425 & 458 & 491 & 524 & 557 & 559 & 592 & 625 \newline 690 & 723 & 756 & 789 & 822 & 855 & 888 & 921 & 954 & 26 & 59 & 92 & 94 & 127 & 160 & 193 & 226 & 259 & 292 & 325 & 358 & 391 & 424 & 457 & 490 & 523 & 556 & 589 & 591 & 624 & 657 \newline 722 & 755 & 788 & 821 & 854 & 887 & 920 & 953 & 25 & 58 & 91 & 124 & 126 & 159 & 192 & 225 & 258 & 291 & 324 & 357 & 390 & 423 & 456 & 489 & 522 & 555 & 588 & 590 & 623 & 656 & 689 \newline 754 & 787 & 820 & 853 & 886 & 919 & 952 & 24 & 57 & 90 & 123 & 125 & 158 & 191 & 224 & 257 & 290 & 323 & 356 & 389 & 422 & 455 & 488 & 521 & 554 & 587 & 620 & 622 & 655 & 688 & 721 \newline 786 & 819 & 852 & 885 & 918 & 951 & 23 & 56 & 89 & 122 & 155 & 157 & 190 & 223 & 256 & 289 & 322 & 355 & 388 & 421 & 454 & 487 & 520 & 553 & 586 & 619 & 621 & 654 & 687 & 720 & 753 \newline 818 & 851 & 884 & 917 & 950 & 22 & 55 & 88 & 121 & 154 & 156 & 189 & 222 & 255 & 288 & 321 & 354 & 387 & 420 & 453 & 486 & 519 & 552 & 585 & 618 & 651 & 653 & 686 & 719 & 752 & 785 \newline 850 & 883 & 916 & \mathbf{949} & 21 & 54 & 87 & 120 & 153 & 186 & 188 & 221 & 254 & 287 & 320 & 353 & 386 & 419 & 452 & 485 & 518 & 551 & 584 & 617 & 650 & 652 & 685 & 718 & 751 & 784 & 817 \newline 882 & 915 & 948 & 20 & 53 & 86 & 119 & 152 & 185 & 187 & 220 & 253 & 286 & 319 & 352 & 385 & 418 & 451 & 484 & 517 & 550 & 583 & 616 & 649 & 682 & 684 & 717 & 750 & 783 & 816 & 849 \newline 914 & 947 & 19 & 52 & 85 & 118 & 151 & 184 & 217 & 219 & 252 & 285 & 318 & 351 & 384 & 417 & 450 & 483 & 516 & 549 & 582 & 615 & 648 & 681 & 683 & 716 & 749 & 782 & 815 & 848 & 881 \newline 946 & 18 & 51 & 84 & 117 & 150 & 183 & 216 & 218 & 251 & 284 & 317 & 350 & 383 & 416 & 449 & 482 & 515 & 548 & 581 & 614 & 647 & 680 & 713 & 715 & 748 & 781 & 814 & 847 & 880 & 913 \newline 17 & 50 & 83 & 116 & 149 & 182 & 215 & 248 & 250 & 283 & 316 & 349 & 382 & 415 & 448 & 481 & 514 & 547 & 580 & 613 & 646 & 679 & 712 & 714 & 747 & 780 & 813 & 846 & 879 & 912 & 945 \newline 49 & 82 & 115 & 148 & 181 & 214 & 247 & 249 & 282 & 315 & 348 & 381 & 414 & 447 & 480 & 513 & 546 & 579 & 612 & 645 & 678 & 711 & 744 & 746 & 779 & 812 & 845 & 878 & 911 & 944 & 16 \newline 81 & 114 & 147 & 180 & 213 & 246 & 279 & 281 & 314 & 347 & 380 & 413 & 446 & 479 & 512 & 545 & 578 & 611 & 644 & 677 & 710 & 743 & 745 & 778 & 811 & 844 & 877 & 910 & 943 & 15 & 48 \newline 113 & 146 & 179 & 212 & 245 & 278 & 280 & 313 & 346 & 379 & 412 & 445 & 478 & 511 & 544 & 577 & 610 & 643 & 676 & 709 & 742 & 775 & 777 & 810 & 843 & 876 & 909 & 942 & 14 & 47 & 80 \newline 145 & 178 & 211 & 244 & 277 & 310 & 312 & 345 & 378 & 411 & 444 & 477 & 510 & 543 & 576 & 609 & 642 & 675 & 708 & 741 & 774 & 776 & 809 & 842 & 875 & 908 & 941 & 13 & 46 & 79 & 112 \newline 177 & 210 & 243 & 276 & 309 & 311 & 344 & 377 & 410 & 443 & 476 & 509 & 542 & 575 & 608 & 641 & 674 & 707 & 740 & 773 & 806 & 808 & 841 & 874 & 907 & 940 & 12 & 45 & 78 & 111 & 144 \newline 209 & 242 & 275 & 308 & 341 & 343 & 376 & 409 & 442 & 475 & 508 & 541 & 574 & 607 & 640 & 673 & 706 & 739 & 772 & 805 & 807 & 840 & 873 & 906 & 939 & 11 & 44 & 77 & 110 & 143 & 176 \newline 241 & 274 & 307 & 340 & 342 & 375 & 408 & 441 & 474 & 507 & 540 & 573 & 606 & 639 & 672 & 705 & 738 & 771 & 804 & 837 & 839 & 872 & 905 & 938 & 10 & 43 & 76 & 109 & 142 & 175 & 208 \newline 273 & 306 & 339 & 372 & 374 & 407 & 440 & 473 & 506 & 539 & 572 & 605 & 638 & 671 & 704 & 737 & 770 & 803 & 836 & 838 & 871 & 904 & 937 & 9 & 42 & 75 & 108 & 141 & 174 & 207 & 240 \newline 305 & 338 & 371 & 373 & 406 & 439 & 472 & 505 & 538 & 571 & 604 & 637 & 670 & 703 & 736 & 769 & 802 & 835 & 868 & 870 & 903 & 936 & 8 & 41 & 74 & 107 & 140 & 173 & 206 & 239 & 272 \newline 337 & 370 & 403 & 405 & 438 & 471 & 504 & 537 & 570 & 603 & 636 & 669 & 702 & 735 & 768 & 801 & 834 & 867 & 869 & 902 & 935 & 7 & 40 & 73 & 106 & 139 & 172 & 205 & 238 & 271 & 304 \newline 369 & 402 & 404 & 437 & 470 & 503 & 536 & 569 & 602 & 635 & 668 & 701 & 734 & 767 & 800 & 833 & 866 & 899 & 901 & 934 & 6 & 39 & 72 & 105 & 138 & 171 & 204 & 237 & 270 & 303 & 336 \newline 401 & 434 & 436 & 469 & 502 & 535 & 568 & 601 & 634 & 667 & 700 & 733 & 766 & 799 & 832 & 865 & 898 & 900 & 933 & 5 & 38 & 71 & 104 & 137 & 170 & 203 & 236 & 269 & 302 & 335 & 368 \newline 433 & 435 & 468 & 501 & 534 & 567 & 600 & 633 & 666 & 699 & 732 & 765 & 798 & 831 & 864 & 897 & 930 & 932 & 4 & 37 & 70 & 103 & 136 & 169 & 202 & 235 & 268 & 301 & 334 & 367 & 400 \newline 465 & 467 & 500 & 533 & 566 & 599 & 632 & 665 & 698 & 731 & 764 & 797 & 830 & 863 & 896 & 929 & 931 & 3 & 36 & 69 & 102 & 135 & 168 & 201 & 234 & 267 & 300 & 333 & 366 & 399 & 432 \newline 466 & 499 & 532 & 565 & 598 & 631 & 664 & 697 & 730 & 763 & 796 & 829 & 862 & 895 & 928 & 961 & 2 & \bf{35} & 68 & 101 & 134 & 167 & 200 & 233 & 266 & 299 & 332 & 365 & 398 & 431 & 464 \end{smallmatrix} $$
For e.g., we can locate $949$ in the 12th row and 4th column in the above magic square.
If we consider the $3 \times 3$ square with $949$ in the center, we have
$$ \Delta_{3}(949) = \begin{matrix} 884 & 917 & 950 \newline 916 & 949 & 21 \newline 948 & 20 & 53 \end{matrix} $$
We compute a GCD matrix by taking the GCD of the entry with the center element $949$ in this case i.e., $G_{3}(949)$. For e.g., $\gcd(884, 949) = 13, \gcd(917, 949) = 1, \cdots$.
The GCD matrix of the entries with the center term $949$ is:
$$ G_{3}(949) = \begin{matrix} 13 & 1 & 1 \newline 1 & 949 & 1 \newline 1 & 1 & 1 \end{matrix} $$
$13$ is a non-trivial divisor of $949$ the element in the center of the search grid, $G_{3}(949)$.
When we get to entries in the last row or first row of the magic square, we can wrap around and take the adjacent entries (by the modular arithmetic on the indices mod $n$).
For e.g., entries around $35$:
$$ \Delta_{3}(35) = \begin{matrix} 931 & 3 & 36 & \newline 2 & 35 & 68 & \text{from last row}\newline 34 & 67 & 100 & \text{from first row} \end{matrix} $$
GCD matrix for $35$:
$$ G_{3}(35) = \begin{matrix} 7 & 1 & 1 \newline 1 & 35 & 1 & \text{from last row}\newline 1 & 1 & 5 & \text{from first row} \end{matrix} $$
$7$ and $5$ are non-trivial divisors of $35$ in the search grid.
This led me to conjecture that we can find non-trivial GCDs in a $3 \times 3$ neighborhood of an entry in a larger $n\times n$ magic square. But that is not true.
Counterexample. Entries around $959$:
$$ \Delta_{3}(959) = \begin{matrix} 894 & 927 & 960 \newline 926 & 959 & 31 \newline 958 & 30 & 32 \end{matrix} $$
GCD matrix for $959$:
$$ G_{3}(959) = \begin{matrix} 1 & 1 & 1 \newline 1 & 959 & 1 \newline 1 & 1 & 1 \end{matrix} $$
$959$ doesn't have any non-trivial GCDs in the $3 \times 3$ search grid.
For each of the primes the following table shows the multiples that are found in the $3 \times 3$ neighborhood:
$$ \begin{matrix} \text{p} & \text{multiple in $3\times 3$ neighborhood} \newline \hline 2 & 34 \newline 3 & 36, 930 \newline 5 & 70 \newline 7 & 903 \newline 11 & 44 \newline 13 & 78 \newline 17 & \text{exception} \newline 19 & \text{exception} \newline 23 & \text{exception} \newline 29 & 957 \newline 31 & \text{exception} \newline \end{matrix} $$
For the exception cases, if we expand the GCD matrix to $5 \times 5$ or $7 \times 7$ we find non-trivial multiples in those expanded matrices.
When we expand to $5\times 5$ grid:
- for $17$, we find $51$;
- for $23$ we find $920$;
When we expand to $7 \times 7$ grid:
- for $19$, we find $817, 950$
This brings up some interesting conjectures.
Conjecture 1. For any composite $x$ there is a minimal odd square grid with dimensions $\delta \times \delta$ centered on $x$ that contains entry $y$ with non-trivial $\gcd(x,y)$. An obvious upper bound for $\delta$ is $n$, the dimension of the magic square itself. We conjecture that the minimal odd square grid dimensions $\delta \ll n$.
Can we say anything about the size of the minimal odd square grid for a given $x$?
Can we give a probability of finding an entry $y$ in the neighborhood with a non-trivial $\gcd(x,y)$ in an odd square grid centered on $x$ with dimensions $\delta \times \delta$?
Conjecture 2. For a given $x$ there exists an odd magic square of dimensions $n \times n$ containing $y$ such that a non-trivial $\gcd(x,y)$ lies in a neighborhood grid of dimensions $\delta \times \delta$
Can we prove or disprove this?
If true, can we derive sharp bounds for $n, \delta$ based on $x$.
Conjecture 3. The criteria for the magic square are given in [Apostol51]:
The square is magic iff
- $\alpha, \beta, a$ and $b$ are prime to $n$
- $\begin{vmatrix} \alpha & a\\ \beta & b \end{vmatrix}$ is prime to $n$
So, we conjecture that $\exists \alpha, \beta, a, b$ prime to $n$ and $\begin{vmatrix} \alpha & a\\ \beta & b \end{vmatrix}$ prime to $n$ such that for composite $x = pq, p\ne 1, q\ne 1$, where $p,q$ not necessarily prime, $p$ lies in the $8$-neighborhood of $x$ (i.e., the $3\times 3$ GCD matrix centered on $x$).
- Can we prove this?
- If true, can we devise a method to select the parameters $\alpha, \beta, a, b$ based on $x, n$.
Update on Conjecture 3. 50 primes greater than $10000$ were taken and semi-primes constructed by taking prime pairs from that set. For all those semi-primes $N=pq$, we constructed Uniform Step magic squares using Lehmer's construction with $n = \lceil \sqrt{N} \rceil$. If $n$ was even, we took the next odd number $n+1$. Then, using brute-force, we generated quadruples $(\alpha, \beta, a, b)$ satisfying the magic square conditions. We then solved for the $8$-neighbors of $N$ in the magic square using Eqn. $(1)$ and checked the GCD for non-triviality in the GCD matrix. In every one of those cases, a non-trivial GCD was found, strengthening the conjecture.
A formal proof for all odd $n$, remains to be proven.
Related: See separate related MSE question on improving the brute-force algorithm for generating the quadruples.
References:
[Apostol51]: Apostol, T. M., and Herbert S. Zuckerman. “On Magic Squares Constructed by the Uniform Step Method.” Proceedings of the American Mathematical Society, vol. 2, no. 4, 1951, pp. 557–65. JSTOR, https://doi.org/10.2307/2032007. Accessed 17 Aug. 2023.