Biquadratic SOS Rank and Double Zarankiewicz Number

본 논문은 $m \times n$ 이차형식의 최대 SOS 랭크 하한을 개선하기 위해 일반 $C_4$-사이클을 포함하지 않는 일반화된 이분 그래프를 기반으로 한 '이중 자란키에비치 수' $z_2(m,n)$을 정의하고, 이를 통해 기존 하한을 넘어선 새로운 하한을 제시하며 $4\times4$및$5\times3$ 등 다양한 매개변수에 대한 정확한 값을 구하거나 범위를 설정합니다.

핵심

📝 제목: "이중 자란키에비치 수"와 "완벽한 제곱의 비밀"

1. 배경: "네모난 상자"와 "금지된 모양"

상상해 보세요. 여러분은 **행 (Rows)**과 **열 (Columns)**로 이루어진 거대한 격자판 (표) 을 가지고 있습니다.

• 행은 '사람 A, B, C...'
• 열은 '사과, 오렌지, 바나나...'
  라고 생각합시다.

이 표의 칸에 **선 (Edge)**을 그어 사람과 과일을 연결한다고 칩시다. 여기서 중요한 규칙이 하나 있습니다.

"어떤 두 사람과 두 과일 사이에도 네모난 모양 (사각형) 이 만들어지면 안 됩니다."

예를 들어, A-사과, A-오렌지, B-사과, B-오렌지 이렇게 네 개의 선이 모두 연결되면 '네모'가 생기는데, 이것이 **금지된 모양 (C4 사이클)**입니다.

수학자들은 이 규칙을 지키면서 가장 많은 선을 그을 수 있는 방법을 오랫동안 연구해 왔습니다. 이를 **'자란키에비치 수 (Zarankiewicz number)'**라고 부릅니다. 마치 "네모를 만들지 않고 최대한 많은 친구 관계를 맺을 수 있는 최대 인원"을 찾는 문제와 같습니다.

2. 문제: "예상보다 더 많은 선을 그을 수 있다?"

최근 연구에서 흥미로운 일이 발견되었습니다.

• **4 명 (행) 과 3 가지 과일 (열)**의 경우, 기존 이론에 따르면 네모를 만들지 않고 그을 수 있는 선의 최대 개수는 7 개였습니다.
• 하지만 연구자들은 8 개까지 그을 수 있는 새로운 방법을 찾아냈습니다!

어떻게 가능했을까요? 그들은 단순히 선을 그리는 것뿐만 아니라, **"두 개의 선을 묶어서 하나의 강력한 선 (이중 선)"**처럼 취급하는 새로운 규칙을 도입했습니다.

• 기존: A-사과 (단순 선)
• 새로운 것: (A-사과) + (B-오렌지)를 하나로 묶어서 제곱하는 형태.

이런 새로운 방식은 마치 **"두 개의 친구 관계를 묶어서 하나의 강력한 유대감으로 간주하는 것"**과 같습니다. 이렇게 하면 기존 규칙 (네모 금지) 을 위반하지 않으면서도 더 많은 관계를 표현할 수 있게 됩니다.

3. 새로운 개념: "이중 자란키에비치 수 (Double Zarankiewicz Number)"

논문의 저자들은 이 현상을 설명하기 위해 **'이중 자란키에비치 수 ($z_2$)'**라는 새로운 개념을 만들었습니다.

• 1-선 (Ordinary Edge): 일반적인 연결 (예: A-사과).
• 2-선 (Double Edge): 두 개의 연결을 묶은 것 (예: (A-사과) + (B-오렌지)).

이제 문제는 **"네모 모양을 만들지 않으면서, 1-선과 2-선을 합쳐서 그을 수 있는 최대 개수는 얼마인가?"**가 됩니다.

4. 주요 발견: "작은 숫자일수록 놀라운 결과"

저자들은 작은 숫자 (행과 열의 개수) 를 가지고 실험을 해보았습니다.

• 3x3 경우: 기존 이론과 동일하게 6 개. (변화 없음)
• 4x3 경우: 기존 이론은 7 개였지만, 새로운 방법으로 8 개까지 가능함을 증명했습니다. (기존보다 1 개 더 많음!)
• 5x3 경우: 기존 이론은 8 개였지만, 새로운 방법으로 9 개까지 가능함을 증명했습니다.
• 4x4 경우: 기존 이론은 9 개였지만, 새로운 방법으로 최소 10 개는 가능함을 보였습니다. (정확한 최대값은 아직 미스터리로 남아있지만, 11 개는 불가능할 것 같다고 추측합니다.)

이 발견은 수학적으로 매우 중요합니다. 왜냐하면 이 '선들의 개수'가 바로 **수식의 복잡도 (SOS Rank)**를 나타내기 때문입니다.

5. 왜 중요한가요? "수식의 최소 조각 수"

이 논문에서 다루는 '이중 선'들은 실제로 **수학적인 '제곱의 합 (Sum of Squares)'**을 나타냅니다.

• 어떤 복잡한 수식을 만들 때, **최소 몇 개의 '제곱수'를 더해야 그 수식을 표현할 수 있을까?**를 묻는 문제가 있습니다.
• 이 논문은 "기존에 생각했던 것보다 더 많은 제곱수 (복잡한 수식) 가 필요할 수 있다"는 것을 증명했습니다.

비유하자면:

"우리는 레고 블록으로 탑을 쌓는다고 칩시다. 기존 이론은 '네모난 구조를 피하면 7 개 블록으로 충분하다'고 했습니다. 하지만 저자들은 '특정 블록을 두 개 붙여서 하나의 강력한 블록으로 쓰면, 8 개 블록으로 더 튼튼하고 복잡한 탑을 지을 수 있다'고 증명했습니다."

6. 결론: "새로운 지도를 발견하다"

이 논문은 다음과 같은 의미를 가집니다:

1. 새로운 규칙의 발견: 단순히 선을 그리는 것뿐만 아니라, 선들을 묶는 새로운 방식 (2-선) 을 도입하면 더 많은 정보를 담을 수 있음을 보였습니다.
2. 한계점의 확장: 4x3, 5x3 같은 작은 경우에서 기존 이론의 한계를 깨뜨렸습니다.
3. 미래의 과제: 4x4 경우의 정확한 최대값이 10 인지 11 인지는 아직 미해결 문제입니다. 또한 더 큰 숫자 (5x5 이상) 에서는 어떤 일이 일어날지 아직 알 수 없습니다.

한 줄 요약:

"수학자들은 네모 모양을 만들지 않고 최대한 많은 연결을 찾는 게임에서, 기존에 몰랐던 '이중 연결'이라는 새로운 규칙을 발견하여 더 많은 연결을 가능하게 만들었습니다. 이는 복잡한 수식을 만드는 데 필요한 최소 조각 수를 다시 생각하게 만드는 중요한 발견입니다."

이 연구는 **그래프 (그림)**와 **대수 (수식)**가 서로 어떻게 영향을 주고받는지 보여주는 아름다운 예시입니다.

기술 요약

1. 연구 배경 및 문제 제기 (Problem)

• 배경: $m \times n$ 이차형식 $P(x, y)$의 SOS 랭크 (최소 제곱 항의 개수) 의 최댓값을 $BSR(m, n)$으로 정의합니다. 기존 연구에 따르면, $BSR(m, n)$은 고전적인 자란키에비치 수 (Zarankiewicz number) $z(m, n)$에 의해 하한이 결정됩니다. 여기서 $z(m, n)$은 $C_4$ (4-사이클) 를 포함하지 않는 이분 그래프의 최대 간선 수입니다.
• 문제점: $4 \times 3$ 사례에서 기존 이론과 모순되는 현상이 발견되었습니다.
  • 고전적 자란키에비치 수: $z(4, 3) = 7$.
  • 실제 SOS 랭크 하한: $BSR(4, 3) \ge 8$.
  • 원인: 단순한 이차형식 (단항식 제곱의 합) 에, 두 항의 곱으로 이루어진 이차형식의 제곱 $(x_4y_2 + x_1y_3)^2$을 추가함으로써 SOS 랭크가 7 에서 8 로 증가하는 구조가 발견되었습니다. 이는 단순한 그래프 간선 (1-간선) 만으로는 설명할 수 없는 현상입니다.
• 연구 목표: 이러한 현상을 설명하기 위해 이중 자란키에비치 수 $z_2(m, n)$을 도입하고, 이를 통해 $BSR(m, n)$의 하한을 더 정밀하게 추정하는 것입니다.

2. 방법론 (Methodology)

저자들은 그래프 이론과 대수적 기하학을 결합한 새로운 프레임워크를 제시합니다.

A. 이중 그래프 및 이중 단순 이차형식 (Doubly Simple Biquadratic Form)

• 그래프 정의: 정점 집합 $S=\{1, \dots, m\}$과 $T=\{1, \dots, n\}$을 가진 이분 그래프 $G$를 정의하되, 간선 집합을 두 가지로 나눕니다.
  • 1-간선 (1-edge): $(i, j)$ 형태. 이는 $x_i^2 y_j^2$ 항에 대응.
  • 2-간선 (2-edge): $(i, j; k, l)$ 형태. 이는 $(x_i y_j + x_k y_l)^2$ 항에 대응. (단, $i=k$이거나 $j=l$일 수는 있지만 둘 다 같을 수는 없음).
• 연결된 다항식: 그래프 $G$에 대응하는 다항식 $P_G(x, y)$는 다음과 같이 정의됩니다.
  $$P_G(x, y) = \sum_{(i,j) \in E_1} x_i^2 y_j^2 + \sum_{(i,j;k,l) \in E_2} (x_i y_j + x_k y_l)^2$$

B. 일반화된 $C_4$-사이클 (Generalized $C_4$-cycle)

• SOS 랭크가 간선의 총합 ($|E_1| + |E_2|$) 과 일치하기 위한 필요충분 조건으로 일반화된 $C_4$-사이클의 부재를 정의합니다.
  1. 조건 (i) (계수적 조건): 임의의 $2 \times 2$ 서브행렬 (두 행과 두 열) 에서, 1-간선은 1 개, 2-간선은 두 개의 일반 간선으로 간주하여 계산했을 때 총 간선 수가 4 이상이면 안 됩니다.
  2. 조건 (ii) (선형 독립 조건): 해당 $2 \times 2$ 블록 내에서 생성된 기저 벡터들의 선형 결합이 0 이 되는 비자명한 (nontrivial) 관계가 존재하지 않아야 합니다.
• 이중 자란키에비치 수 $z_2(m, n)$: 일반화된 $C_4$-사이클을 포함하지 않는 $m \times n$ 이분 그래프에서 가능한 최대 간선 수 ($|E_1| + |E_2|$) 로 정의합니다.

C. 주요 정리 (Theorem 2.4)

• 일반화된 $C_4$-사이클이 없는 그래프 $G$에 대응하는 $P_G$는 **기약 (irreducible)**이며, 그 SOS 랭크는 정확히 $|E_1| + |E_2|$입니다.
• 따라서, $BSR(m, n) \ge z_2(m, n)$이 성립합니다.

3. 주요 결과 (Key Results)

저자들은 다양한 매개변수에 대해 $z_2(m, n)$의 정확한 값을 계산하거나 범위를 설정했습니다.

매개변수 $(m, n)$	고전적 $z(m, n)$	이중 $z_2(m, n)$	비고
$(m, 2)$	$m+1$	$m+1$	$z_2(m, 2) = m+1$
$(2, n)$	$n+1$	$n+1$	$z_2(2, n) = n+1$
$(3, 3)$	6	6	$z_2(3, 3) = 6$
$(4, 3)$	7	8	새로운 하한 발견 ($BSR(4, 3) \ge 8$)
$(5, 3)$	8	9	새로운 하한 발견 ($BSR(5, 3) \ge 9$)
$(4, 4)$	9	$10 \le z_2 \le 11$	개방적 문제 (하한 10 증명, 상한 11)

• **$4 \times 3$및$5 \times 3$사례:** 2-간선을 포함하는 구체적인 그래프 구성을 통해 기존$z(m, n)$보다 큰 값을 달성함을 증명했습니다.
• $4 \times 4$ 사례:
  • 하한: 8 개의 1-간선과 2 개의 2-간선으로 구성된 그래프를 제시하여 $z_2(4, 4) \ge 10$을 증명했습니다. 이는 기존 $z(4, 4)=9$를 상회합니다.
  • 상한: 계수적 논증 (counting argument) 을 통해 $z_2(4, 4) \le 11$임을 보였습니다.
  • 미해결: 정확한 값이 10 인지 11 인지는 아직 밝혀지지 않았습니다. 저자들은 10 일 것이라고 추측합니다.

4. 의의 및 기여 (Significance)

1. SOS 랭크 하한의 개선: $BSR(4, 4)$와 $BSR(5, 3)$에 대한 기존 하한을 개선했습니다. 특히 $4 \times 3$ 사례에서 발생한 "갭 (gap)"을 이론적으로 설명하고 일반화했습니다.
2. 새로운 조합론적 불변량 도입: 자란키에비치 문제를 "이중 간선"을 허용하는 형태로 확장하여, SOS 표현의 복잡성과 그래프 구조 사이의 새로운 연결고리를 제시했습니다.
3. 이론적 통찰: SOS 랭크가 단순히 그래프의 간선 수 ($C_4$-free) 에만 의존하는 것이 아니라, 특정 형태의 2-항 제곱 (bilinear form squares) 을 포함할 때 더 높은 랭크를 가질 수 있음을 보였습니다.
4. 미래 연구 방향:
   • $z_2(4, 4)$의 정확한 값 결정.
   • 더 큰 $m, n$에 대한 점근적 행동 분석.
   • 일반화된 $C_4$-사이클 조건을 선형대수적 계산을 통해 효율적으로 검증하는 알고리즘 개발.

결론

이 논문은 이차형식의 SOS 랭크 문제를 해결하기 위해 그래프 이론의 자란키에비치 문제를 확장한 이중 자란키에비치 수를 도입했습니다. 이를 통해 $4 \times 3$및$5 \times 3$과 같은 특정 사례에서 기존 하한을 깨는 새로운 하한을 증명했으며,$4 \times 4$ 사례에서도 하한을 10 으로 높였습니다. 이는 극단 그래프 이론과 SOS 표현 이론 간의 깊은 상호작용을 보여주며, 향후 SOS 랭크의 정확한 한계를 규명하는 데 중요한 기초를 제공합니다.