A Salem-Spencer-Type Construction for Large Subsets of Integer Grids with No Isosceles Right Triangles

당신이 격자 교차점들로만 이루어진 거대하고 무한한 도시에서 미스터리를 풀려는 탐정이라고 상상해 보십시오. 이 도시는 수학의 한 분야인 조합론(Combinatorics), 즉 이산적인 대상들을 세고, 배열하고, 패턴을 찾는 학문의 세계입니다. 이곳에서 "거리"는 단순히 숫자이며, "건물"은 두 숫자가 만나는 지점인 $(x, y)$ 좌표와 같은 점들입니다.

이 미스터리는 매우 구체적인 규칙을 다룹니다. 당신은 특정 모양이 엄격히 금지된 최대한 큰 규모의 이웃(점들의 부분 집합)을 구축하고자 합니다. 그 모양은 바로 직각 이등변 삼각형입니다. 당신은 이 삼각형을 잘 알고 있습니다. 이 삼각형은 한 모서리가 완벽한 90도 각도(종이의 모서리처럼)를 이루며, 그 모서리에 맞닿은 두 변의 길이가 정확히 같습니다. 질문은 수학자들이 오랫동안 던져온 것입니다. 우리가 실수로 이러한 삼각형을 만들지 않으면서, 이 이웃을 얼마나 크게 만들 수 있을까? 이는 단순한 기하학 게임이 아닙니다. 이것은 숫자가 어떻게 행동하는지, 데이터를 어떻게 암호화하는지, 그리고 우리가 우주의 구조를 어떻게 이해하는지와 연결되는 깊은 퍼즐입니다. 만약 당신이 삼각형이 없는 거대한 이웃을 찾아낼 수 있다면, 그것은 숫자를 배치할 때 단순한 패턴을 피하는 숨겨지고 복잡한 방법들이 존재함을 의미합니다. 수십 년 동안 수학자들은 그 답이 "매우 크다"와 "도시의 거의 전체에 가깝다" 사이 어딘가에 있다는 것을 알고 있었습니다. 하지만 가장 큰 가능한 이웃과 가장 작은 가능한 이웃 사이의 간극은 엄청났습니다. 그것은 마치 보물 상자가 사막 어딘가에 있다는 것은 알지만, 그것이 모래 한 알 아래에 묻혀 있는지 아니면 거대한 산 아래에 있는지 알지 못하는 것과 같았습니다.

---

논문의 위대한 발견: "삼각형이 없는" 도시를 만드는 새로운 방법

이 논문에서 두 수학자, 귤라 카로이(Gyula Károlyi)와 요제프 솔리모시(József Solymosi)는 이전에는 가능하다고 생각했던 것보다 훨씬 더 큰 규모의 새로운 이웃을 구축했습니다. 그들은 격자 내에서 직각 이등변 삼각형을 피하는 점들의 부분 집합을 만들어냈으며, 그들의 구성 방식은 그 크기가 격자의 크기($n$)에 대해 대략 $n^{1.3}$의 비율로 성장한다는 것을 증명할 만큼 거대합니다.

이 과정을 이해하기 위해, 당신이 블록으로 탑을 쌓으려고 하는데, 특정 "나쁜" 모양을 형성하는 방식으로 블록을 쌓아서는 안 된다는 엄격한 규칙이 있다고 상상해 보십시오. 과거에 수학자들은 완전히 안전한 블록들을 골라내는 방식으로 이 탑을 쌓으려 노력했습니다. 하지만 카로이와 솔리모시는 더 똑똑하게 행동할 수 있다는 것을 깨달았습니다. 그들은 **"껍질 벗기기(peeling)"**라고 불리는 기술을 사용했는데, 이는 마치 젠가 게임과 같아서, 전체가 안전해질 때까지 특정 순서에 따라 블록을 하나씩 제거할 수 있다면 약간 흔들리는 탑이라도 괜찮다는 원리입니다.

마법의 재료들

저자들은 이를 성공시키기 위해 몇 가지 영리한 기교를 사용했습니다:

1. 가우스 정수 (The "Magic Grid"): 일반적인 숫자를 사용하는 대신, 그들은 가우스 정수라고 불리는 특별한 종류의 숫자를 사용했습니다. 이것을 격자 위의 점들로 생각하면, 모든 점은 $x$ 좌표와 $y$ 좌표를 가지지만, 이들은 하나의 마법 같은 숫자로 취급됩니다. 이를 통해 그들은 일반적인 숫자로는 할 수 없는 방식으로 블록을 회전시키고 이동시킬 수 있었습니다.
2. "올림이 없는" 알파벳: 숫자를 더할 때, 때때로 "올림"이 발생합니다(예를 들어 $9 + 1 = 10$일 때 1이 올라가는 것과 같습니다). 저자들은 만약 이 숫자들을 더해 삼각형을 만들더라도, 다음 단계로 "올림"이 절대 발생하지 않는 특별한 "숫자들"(작은 점들의 집합)을 찾아냈습니다. 덕분에 국소적인 규칙이 단순하게 유지되었습니다.
3. 껍질 벗기기 순서 (비법): 이 부분이 가장 참신한 부분입니다. 그들은 한꺼번에 관찰했을 때 삼각형을 포함하는 281개의 점들을 찾아냈습니다. 그러나 그들은 이 점들을 제거하는 특정한 순서를 발견했습니다. 만약 첫 번째 점을 제거하면, 그 점을 꼭짓점으로 하는 삼각형은 남지 않습니다. 그다음 점을 제거하고, 또 그다음 점을 제거하는 식입니다. 이 과정을 마치고 나면, 남은 집합은 완벽하게 안전해집니다. 이것은 마치 사람들이 원을 그리며 손을 잡고 있는 방에서, 특정 순서대로 나가라고 요청하면 원이 깨지기 전에 아무도 다치지 않고 흩어지는 것과 같습니다.

결과: 거대한 도약

그들은 자신들의 데모를 찾기 위해 수백만 개의 가능성을 탐색하는 데 도움을 주는 AlphaEvolve라는 강력한 AI 도구를 사용하여, 281개의 점들에 대한 "껍질 벗기기 순서"를 찾아냈습니다.

크기가 $n$인 격자에 이 방법을 적용했을 때, 그들은 적어도 $n^{1.3178...}$의 크기를 가진 삼각형 없는 부분 집합을 찾을 수 있음을 증명했습니다.

이를 비교해 보자면:

• 이 전에는 최선의 하한선(lower bound)이 훨씬 작았습니다(약 $n^{1.05}$).
• 알려진 최선의 상한선(upper bound, 이론적 한계)은 대략 $n^2$을 로그 인자들로 나눈 값입니다.
• 그들의 결과인 $n^{1.3}$은 이 상당한 간극을 메우며, 이러한 삼각형 없는 이웃이 이전에 생각했던 것보다 훨씬 더 클 수 있음을 보여줍니다.

그들이 하지 않은 것

이 논문이 주장하지 않는 바를 명시하는 것이 중요합니다. 그들은 $n^{1.3}$이 가능한 절대적인 최대 크기라고 증명한 것이 아닙니다. 그들은 수학적으로 가능한 가장 큰 "완벽한" 이웃을 찾은 것도 아닙니다. 또한 281이 그들의 특정 방법에서 사용할 수 있는 가장 큰 점의 개수라는 것도 증명하지 않았습니다. 단지 매우 좋은 값을 찾아냈을 뿐입니다.

논문은 그들의 새로운 하한선($n^{1.3}$)과 상한선($n^2$) 사이에 여전히 "큰 간극"이 존재한다고 명시하고 있습니다. 미스터리가 완전히 풀린 것은 아니지만, 그들은 이전에 그 누구보다도 훨씬 더 큰 퍼즐 조각을 찾아낸 것입니다.

핵심 요약

이 논문은 고전적인 수학적 논리와 현대적인 AI 탐색을 결합한 승리입니다. 숫자를 격자 위의 점으로 취고, 특별한 "올림 없는" 구역을 찾고, 위험한 점들을 하나씩 제거하는 영리한 "껍질 벗기기" 전략을 사용함으로써, 저자들은 우리가 생각했던 것보다 훨씬 더 큰 "삼각형 없는" 도시를 건설할 수 있음을 보여주었습니다. 이는 문제를 정적인 벽이 아니라, 제거를 통한 동적인 과정으로 바라봄으로써 숫자의 세계에서 새로운 가능성을 열 수 있다는 것을 보여주는 생생한 사례입니다.