論文の概要: Exact values and exact upper bounds for families of integers with arithmetic progression intersections (Erdős Problem #272)

• arxiv url: http://arxiv.org/abs/2607.23004v1
• Date: Sat, 25 Jul 2026 02:45:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-28 22:34:14.963918
• Title: Exact values and exact upper bounds for families of integers with arithmetic progression intersections (Erdős Problem #272)
• Title（参考訳）: 算術進行交叉をもつ整数族に対する厳密な値と正確な上界(エルデシュ問題#272)
• Abstract要約: Szabo の予想は、ある元が極大族の全集合に存在することを証明している。 我々は、星のない極端家族に対する最初の構造的制約を証明した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Let $t(N)$ be the largest $t$ for which there exist distinct sets $A_1,\dots,A_t \subseteq \{1,\dots,N\}$ such that $A_i \cap A_j$ is a nonempty arithmetic progression for all $i \neq j$ (Erdos Problem #272). Simonovits and Sos proved $t(N)=O(N^2)$ and conjectured $\binom{N}{2}+1$ is best possible; Szabo disproved this by a construction giving $t(N) \geq \binom{N}{2}+1+\lfloor(N-1)/4\rfloor$, proved the asymptotics $t(N)=N^2/2+O(N^{5/3}(\log N)^3)$, and asked whether $t(N)=\binom{N}{2}+O(N)$ and whether some element lies in all sets of any extremal family (the kernel question). We determine $t(N)$ exactly for all $3 \leq N \leq 12$ by exhaustive computation: in this entire range Szabo's lower bound is exact, and we conjecture that $t(N)=\binom{N}{2}+1+\lfloor(N-1)/4\rfloor$ for every $N$. Towards the matching upper bound we prove, for every $N$, that Szabo's bound is the exact maximum over all families with a common element (starred families). The proof combines a self-contained ``defect-one'' counting inequality for staircase regions with a new structural theorem: every non-progression member of such a family contains a bad pair that no other member can share. Consequently the sharpened conjecture reduces to a single remaining statement, namely Szabo's kernel conjecture that some element lies in all sets of an extremal family, and we prove first structural constraints on putative non-starred extremal families.
• Abstract（参考訳）: A_1,\dots,A_t \subseteq \{1,\dots,N\}$ とすると、$A_i \cap A_j$ はすべての$i \neq j$ (Erdos Problem #272) に対する空でない算術進行である。 Simonovits and Sos proved $t(N)=O(N^2)$ and conjectured $\binom{N}{2}+1$ is best possible; Szabo disproved that a construction given $t(N) \geq \binom{N}{2}+1+\lfloor(N-1)/4\rfloor$, proved the asymptotics $t(N)=N^2/2+O(N^{5/3}(\log N)^3)$, $t(N)=\binom{N}{2}+O(N)$。 総和で$t(N)$を$3 \leq N \leq 12$に対して$t(N)$と判定し、この範囲で Szabo の下限は正確に、$t(N)=\binom{N}{2}+1+\lfloor(N-1)/4\rfloor$ for every $N$と推測する。 一致する上界に向けて、すべての$N$に対して、Szabo の有界が共通の元を持つすべての族(スター付き族)の正確な最大値であることを証明する。 この証明は、階段領域に対する自己完結した ``defect-one'' カウントの不等式と、新しい構造定理を組み合わせている:そのような家族のすべての非プログレッシブなメンバーは、他のメンバーが共有できない悪いペアを含んでいる。 その結果、シャープ化された予想は、 Szabo の核予想(英語版)と呼ばれる、ある要素が極端族の全集合に存在するという1つの残余の主張に還元され、非スター付き極端族に対する最初の構造的制約が証明される。

関連論文リスト

• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• Extremal Chowla sets and their linear analogues: A human-AI mathematical investigation using Co-Scientist [0.9505505917924889]
  正確な式 $C(L/K)=[L:K]-d_max(L/K)$ を証明する。 有限体に対しては、正規基底構成を用いてすべての次数の直接証明を与える。
  論文  参考訳（メタデータ） (2026-07-25T01:46:56Z)
• Infinite families of APN permutations in constrained trivariate classes over $\mathbb{F}_{2^m}$ [2.771610203951056]
  我々は、Li-KaleyskiのAPN置換ファミリーを2つ拡張する。 特に、$q=2$と$7nmid m$のとき、すべての良い$aneq 1$は、Li-カリースキーと同値なAPN置換CCZを与える。
  論文  参考訳（メタデータ） (2026-03-16T11:41:24Z)
• An Efficient Computational Framework for Discrete Fuzzy Numbers Based on Total Orders [41.99844472131922]
  我々は、$textitpos$関数を計算するために、合計(許容可能な)順序の構造を利用するアルゴリズムを導入する。 提案手法は、下層の鎖の大きさの2乗である$mathcalO(n2 m log n)$の複雑さを実現する。 その結果、この定式化は計算コストを大幅に削減することを示した。
  論文  参考訳（メタデータ） (2025-11-21T09:35:07Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  複素ヒルベルト空間上で作用するエルミート作用素 $A$ を 2n$ とする。 A$ がパウリ拡大において小さな次数を持つとき、あるいは言い換えれば、$A$ は局所 $n$-量子ハミルトニアンである。 A$ が $d$-local, textiti.e., $deg(A)le d$ であるときは常に、次の離散化型不等式を持つことを示す。
  論文  参考訳（メタデータ） (2025-09-15T14:26:11Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。 我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。 また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
  論文  参考訳（メタデータ） (2024-06-07T08:26:31Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。 NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
  論文  参考訳（メタデータ） (2024-02-23T12:22:03Z)
• Bounds on $k$-Uniform Quantum States [22.266687858571363]
  我々は、$(mathbbCd)otimes N$における$k$-uniform状態の存在に対するパラメータ$k$の新しい上限を提供する。 a $k$-uniform state in $(mathbbCd)otimes N$ は純 $(N,1,k+1)_d$ 量子誤り訂正符号に対応するため、最小距離 $k+1$ of pure $(N,1,k+1))_d$ 量子誤り訂正符号にも新たな上限を与える。
  論文  参考訳（メタデータ） (2023-10-10T07:38:13Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)
• Some convergent results for Backtracking Gradient Descent method on Banach spaces [0.0]
  bf Theorem.$X$をバナッハ空間とし、$f:Xrightarrow mathbbR$を$C2$関数とする。 $mathcalC$ を $f$ の臨界点の集合とする。
  論文  参考訳（メタデータ） (2020-01-16T12:49:42Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。