The least quadratic residue and integers represented by quadratic forms

기술 요약: 최소 이차 잉여와 이차 형식에 의해 표현되는 정수

문제 정의
본 논문은 $n$에 대한 최소 비자명 축소 이차 잉여(least non-trivial reduced quadratic residue)인 $\ell(n)$을 조사한다. 구체적으로, $\ell(n)$은 $\gcd(r, n) = 1$이고 $r \equiv x^2 \pmod n$을 만족하는 정수 $x$가 존재하는 가장 작은 제곱수가 아닌 정수 $r > 1$이다. 저자들은 $n$의 크기와 그 소인수의 개수 $\omega(n)$ 모두에 관하여 $\ell(n)$의 상한(bounds)을 설정하고자 한다. 부차적인 목표는 이러한 결과들을 적용하여, 유계된 판별식(bounded discriminant)을 가진 이항 이차 형식(binary quadratic forms)의 가문들이 모든 양의 정수를 큰 경계 $N$까지 표현하는 속도를 결정하는 것이다.

방법론
저자들은 조합론적 논증, 해석적 정수론, 그리고 유한체 위의 대수적 구조를 결려한 방법을 사용한다.

1. 조합론 및 비둘기집 원리: $\ell(n)$의 상한은 비둘기집 원리를 사용하여 도출된다. 산술 급수 내의 소수들과 레장드르 기호(Legendre symbol) 값을 고려함으로써, 저자들은 필요한 이차 잉여 조건을 만족하는 두 소수의 곱이 존재함을 입증한다.
2. 대수적 구성 (하한): 예상외로 큰 $\ell(n)$을 갖는 $n$을 구성하기 위해, 저자들은 소수와 $\mathbb{F}_2$ 위에서의 기약 다항식 사이의 대응 관계를 활용한다. 저자들은 $\mathbb{F}_2$의 대수적 폐체 내의 다항식 근들에 기초하여 완전 곱셈 함수 $f_j: \mathbb{N} \to \{-1, 1\}$를 정의한다. 뉴턴 항등식과 관련된 $\mathbb{F}_2$ 내 서로 다른 원소들의 거듭제곱 합에 관한 핵심 보조정리를 사용하여, 만약 제곱수가 아닌 정수 $r$이 모든 $j$에 대해 $f_j(r) = 1$을 만족하면 $r$은 반드시 커야 함을 증명한다.
3. 해석적 정수론 및 영 밀도 추정(Zero-Density Estimates): $n$의 구성은 주어진 범위 내의 모든 기본 판별식 $D$에 대하여, 해당 집합 내의 적어도 하나의 소수가 $D$에 대한 이차 비잉여(quadratic non-residue)가 되도록 하는 소수 집합을 찾는 것에 의존한다.
   • GRH(일반화 리만 가설) 가정 시: GRH는 소수에 대한 캐릭터 합(character sums)을 제한하는 데 사용되며, 이를 통해 대략 $\exp(C \log \Delta \log \log \Delta)$ 크기의 소수 집합이 존재함을 보장한다.
   • 무조건적(Unconditional) 결과: GRH를 가정하지 않을 경우, 저자들은 디리클레 $L$-함수의 영 밀도 추정치를 활용한다. 저자들은 영의 위치(영 없는 영역)에 따라 판별식 집합을 분할하고, 특정 가중치 함수 $w(t)$를 포함한 가중 합 논증을 적용하여 요구되는 소수의 존재를 확립한다.
4. 이차 형식에 대한 응용: 결과들은 이항 이차 형식 $f(x,y) = ax^2 + bxy + cy^2$에 의한 정수 표현에 적용된다. 저자들은 정수 $n$이 판별식 $D$를 갖는 형상에 의해 표현될 필요충분조건이 $D$가 $4n$에 대해 제곱(modulo $4n$)이라는 사실을 활용한다.

주요 기여 및 결과

• 소인수 개수에 따른 $\ell(n)$의 경계:

  • 상한: $k$를 $n$의 홀수 소인수의 개수라고 할 때, $\ell(n) \le C k 2^{4k}$이며 여기서 $C$는 절대 상수이다.
  • 하한: 각 $k \ge 2$에 대하여, 정확히 $k$개의 서로 다른 소인수를 갖는 무수히 많은 홀수 $n$이 존재하여 $\ell(n) \ge 4^{k - C k / \log k}$를 만족한다. 이차 잉여의 밀도가 $\asymp 2^{-k}$라는 점을 고려할 때, $\ell(n)$이 $2^k$에 더 가까울 것이라는 예측과 달리 이 결과는 놀랍다.

• 크기 $n$에 따른 $\ell(n)$의 경계:

  • 저자들은 모든 기본 판별식 $D$ ($1 < |D| \le \Delta$)에 대하여, $n$의 소인수 $p$ 중 $\left(\frac{D}{p}\right) = -1$을 만족하는 것이 존재하는 홀수 제곱수가 아닌 정수 $n \le N(\Delta)$를 구성한다.
  • 무조건적 결과: $N(\Delta)$는 $\exp(C \log \Delta (\log \log \Delta)^2)$로 선택될 수 있다.
  • GRH 가정 시: 임의의 $C > 2/\log 2$에 대하여 $N(\Delta)$는 $\exp(C \log \Delta \log \log \Delta)$로 선택될 수 있다.
  • 결과적으로, $\ell(n)$은 무조건적으로 $\exp\left(c \frac{\log n}{(\log \log n)^2}\right)$만큼, GRH 하에서는 $\exp\left(\left(\frac{\log 2}{2} + o(1)\right) \frac{\log n}{\log \log n}\right)$만큼 커질 수 있다.

• 이차 형식에 의한 표현:

  • 부정 형식 (Indefinite Forms): 모든 양의 정수 $N$까지는 판별식 $1 < D_f \le \Delta$를 갖는 어떤 원시적(primitive)이고 비퇴화적인 부정 이항 이차 형식에 의해 표현될 수 있다. 여기서 $\Delta = \exp\left((\log 4 + o(1)) \frac{\log N}{\log \log N}\right)$이다.
  • 양의 확정 형식 (Positive Definite Forms, 조건부): GRH를 가정하면, 모든 양의 정수 $N$까지는 판별식 $|D_f| \le \Delta$를 갖는 어떤 원시적 양의 확정 이항 이차 형식에 의해 표현될 수 있다 (위와 동일한 $\Delta$ 사용).
  • 한계: $\Delta = \exp(c \log N / (\log \log N)^2)$인 경우, $|D_f| \le \Delta$인 그 어떤 원시적 비퇴화 이항 이차 형식에 의해서도 표현되지 않는 양의 정수 $n \le N$이 존재한다. GRH 하에서 이 임계값은 $\exp((\frac{\log 2}{2} - \epsilon) \frac{\log N}{\log \log N})$로 개선된다.

의의 및 주장

본 논문은 최소 이차 잉여에 대하여, 모듈러스의 크기와 소인수의 개수 모두에 관하여 "거의 최적에 가까운 경계(nearly optimal bounds)"를 확립했다고 주장한다. 큰 $\ell(n)$을 갖는 모듈러스의 구성은 오류 수정 코드(error-correcting codes)의 아이디어에서 동기 부여되었으며, 이는 $\ell(n)$이 이차 잉여의 밀도보다 훨씬 더 클 수 있음을 보여줌으로써 확률적 기대치를 뛰어넘는 중요한 진전을 나타낸다.

저자들은 자신의 연구를 원시 이차 캐릭터 $\chi$에 대해 $\chi(p) = -1$을 만족하는 최소 소수 $p$를 찾는 고전적인 문제의 변형으로 위치시킨다. 고전적인 문제는 GRH 하에서 잘 이해되어 있지만, 본 논문은 합성 모듈러스로 그 범위를 확장하고, 조건부 결과보다 약간 약한 수준의 무조건적 결과들을 제공한다.

또한, 본 논문은 유계된 판별식을 가진 이차 형식들을 사용하여 $N$까지의 모든 정수를 덮는(covering) 문제에 대해 정량적인 진전을 제공한다. 이전 연구(Green과 Soundararajan)가 "거의 모든" 정수를 덮는 문제를 다루었다면, 본 논문은 "모든" 정수를 덮는 더 어려운 문제를 다루며, 표현을 보장하기 위해 필요한 판별식의 명시적인 임계값을 확립한다.

마지막으로, 저자들은 길이 $k$의 모든 부호 수열(sign sequences)이 레장드르 기호 벡터로서 나타나기 위해 필요한 최소 $N$에 관한 Hanson, Vaughan, Zhang의 연구와의 연관성을 언급하며, 사용된 조합론적 방법론의 더 넓은 맥락을 시사한다.