数学
Mathematics
代数几何
Algebraic Geometry
代数拓扑学
Algebraic Topology
偏微分方程分析
Analysis of PDEs
Tarski 的 E_2 欧几里得几何学一阶公理系统 E_2 以其完整性和可判定性而著称。 然而,毕达哥拉斯定理 - 无论是在其现代代数形式 a^2+b^2=c^2 还是在欧几里德的元素中 - 都不能直接用E_2表示,因为距离和面积都不是E_2语言中的原始概念。 在本文中,我们引入了一种双排序语言的替代公理系统 E_d ,它以双位距离函数 d 作为唯一的几何原语。 我们还介绍了它的保守扩展E_da,其中还包含一个三位角函数a。 该系统 E_d 有两个显著特征:它简单(具有单一的几何原始),并且是定量的。 数值距离可以用这种语言直接表达。 相似性公理在 E_d 中起着核心作用,用一块石头有效地杀死两只鸟:它为比例和相似性理论提供了严谨的基础,它暗示了欧几里德的平行姿势(EPP)。 相似性公理可以看作是EPP的定量表述。 毕达哥拉斯定理和相似性理论的其他定量结果可以直接用E_d和E_da的语言表达,激励了Quantitative Euclidean Geometry的名称。 传统的分析几何学可以在E_d的合成几何学下统一。 也就是说,解析几何学不被视为E_d的模型,而是其语句可以用E_d的语言表示为一阶形式句子。 系统 E_d 被证明是一致、完整和可决定的。 最后,我们将理论扩展到高维度的双曲几何和欧几里得几何。
考虑使用近似距离查询定位未知目标点的任务:在每一轮中,重建器选择一个查询点,并接收其距离目标的嘈杂版本。 这个问题自然出现在各种环境中,从GPS和传感器网络中的本地化到隐私感知数据访问,并跨越了各种各样的度量空间。 从重建者(寻求准确恢复)和响应者(旨在限制信息披露,例如出于隐私或安全原因)的角度来看,这是相关的。 我们通过学习理论镜头研究这种重建游戏,专注于最佳重建误差的速度和极限。 我们的第一个结果提供了切比舍夫半径的最佳误差的紧密几何特征,这是几何学的经典概念。 此表征适用于所有紧凑度量空间(事实上,甚至适用于所有完全边界的空间),并产生自然度量空间的显式公式。 我们的第二个结果解决了重建的渐近行为,区分了伪有限空间 - 在有限多次查询后达到最佳误差 - 以及近似曲线表现出非平凡衰减的空间。 我们表征了 convex Euclidean 空间的伪有限性。
给定𝐑^d空间中的n个点组成的集合P，以及正整数k ≤ n，k-分散问题是从给定点中选择k个点，使得它们之间的最小点间距离（在欧几里得距离下）最大化。我们展示了以下结果：（I）给定平面中的n个点集合P和正整数k ≥ 2，k-分散问题可以通过运行时间为O(n^k-1logn)的算法求解。这将Horiyama、Nakano、Saitoh、Suetsugu、Suzuki、Uehara、Uno和Wasa（2021）针对k=3的早期结果推广到任意k。特别地，对于较小的k，它改进了之前的运行时间。（II）给定𝐑^3空间中的n个点集合P和正整数k ≥ 2，如果k是偶数，k-分散问题可以通过运行时间为O(n^k-1logn)的算法求解；如果k是奇数，则运行时间为O(n^k-1log^2n)。对于k ≥ 4，此前没有已知的运行时间为o(n^k)的组合算法可以解决此问题。（III）设P是在[0,1]^2中均匀分布的n个随机点组成的集合。那么在适当条件下，可以在O(n)时间内以高概率计算k-分散的0.99近似解。
我们研究环面𝕋^d上最小化具有张量积结构的相互作用能量的点配置，这类问题自然出现在偏差理论和拟蒙特卡罗积分的背景下。𝕋^2上的置换集和高维空间中的拉丁超立方集（即其在坐标轴上的投影是等间距点的集合）是能量最小化的自然候选者。我们证明，在向量意义上仅有一个距离的这类点配置对于广泛的势函数都能最小化能量，换句话说，这类集合满足张量积版本的普适最优性。这特别适用于三点和五点斐波那契格。我们还刻画了具有此性质的所有格，并展示了这类的一些非格集合。此外，我们获得了关于张量积能量的全局和局部最小化器的若干进一步结构结果。
我们研究基于排序的嵌入β_𝐀 : ℝ^n×d→ℝ^n×D, 𝐗↦↓(𝐗𝐀)，其中↓表示矩阵的列排序。此类嵌入出现在图深度学习中，其中输出应对图节点的置换保持不变。先前的工作表明，对于足够大的D和适当的𝐀，映射β_𝐀是单射的，并且满足双Lipschitz条件。然而，仍存在两个空白：首先，单射性所需的最优尺寸D尚不清楚；其次，该映射的双Lipschitz常数的估计尚不可知。在本文中，我们在解决这两个空白方面取得了实质性进展。关于第一个空白，我们改进了单射性所需嵌入维度D的最佳已知上界，并提供了最小单射性维度的下界。关于第二个空白，我们构造了矩阵𝐀，使得β_𝐀的双Lipschitz失真与n呈二次依赖关系，并且完全独立于d。我们还证明了β_𝐀的失真至少为Ω(√(n))。最后，我们通过对β_𝐀应用线性投影以减少其输出维度的变体提供了类似的结果。
几乎正交向矢量的概念,即表观相似度接近0的矢量,涉及纯数学和编码理论的主题,以球形包装和球形代码为幌子。 近年来,人工智能中高级语言模型的兴起对这一概念产生了新的兴趣,因为模型似乎将某些概念存储为高维空间中的几乎正交方向。 在这项调查中,我们通过三种方法代表了关于几乎正交向的一些想法:(1)几乎正交的数学理论,(2)语言模型嵌入空间的一些观察,(3)通过模拟生成大型几乎正交向矢量。
我们显示每个未加权的字符串图 G 都有 O(1)- 失真平面模拟器:即存在一个(边缘加权)平面图 H 与 V(H) = V(G),使每对顶点 (u,v) 满足 δ_G(u,v) ≤δ_H(u,v) ≤ O(1) ·δ_G(u,v,v)。
我们使用线性编程边界来分析图中关于差异理论和准蒙特卡洛方法中问题的最优性。 这些概念将统一引入张量产品能量。 我们表明,任何维度的规范三点格位在托鲁的所有3点组中都是全球最优的,相对于一大类这样的能量。 这是一个普遍最优的新实例,这种特殊现象只以一小类高度结构化的点集而闻名。 在d=2维度的情况下,推测所谓的斐波那契晶格也应该是相对于一大类潜力的最佳选择。 为此,我们表明5点斐波那契晶格在全球范围内是最佳的,用于与准蒙特卡罗方法分析相关的连续参数化级潜力。
我们提出了一个算法,用于用已知对称组的晶格的Voronoi细胞的精确计算机辅助构建。 我们的算法与人脸总数相比,在线方面比线性缩放要好,并且适用于12以外的尺寸,这是以前的方法无法实现的。 新算法应用于Coxeter-Todd 格子K_12以及从层压K_12获得的晶格家族。 通过优化这个家族,我们获得了一个新的13维格位,其量子化常数比提交时的任何已发表的都小。 (关于后续改进,请参阅在结论后添加的注释。
我们证明,对于每个可计数的字符串图 S,有一个带有 V(G)=V(S) 的平面图 G,使得 1/23660800d_S(u,v) ≤ d_G(u,v) ≤ 162 d_S(u,v) ≤ 162 d_S(u,v) 的 u,v ,其中 d_S(u,v), d_G(u,v) 表示 u 和 v 之间的距离。 换句话说,字符串图形是准等距平面图。 这个定理从平面图提升到弦图,我们举了一些例子。 字符串图形最多有Assouad-Nagata(和渐近尺寸)。 连接的,本地有限,准瞬态字符串图是可访问的。 有限生成的组 Γ 实际上是自由和表面组的自由产品,如果并且只有在 Γ 准对字符串图时。 另外两个推论是,可计数平面公制图和完整的黎曼平面平面图也是与平面图的准等距图,它回答了Georgakopoulos和Papasoglu的问题。 对于有限字符串图形和平面公制图,我们的证明产生多项式时间(对于字符串图形,这是以输入中给出的表示的大小而言)算法用于生成这种准等距平面图。
我们设计了一个确定性算法,在典型的恒定度正则图中给定n点,查询O(n)距离以输出这些点之间的平均距离的恒定因子近似,从而回答<cit.>提出的问题。 我们的算法使用 <cit.> 的方法构建了一系列恒定度图,这些图形是相对于某些非正向弯曲度量空间的扩展器,以及用于非正向弯曲度量空间的度量变换的新刚度定理。 我们的算法适用于典型的(均匀随机的)恒定度正则图形而不是所有恒定度图的事实是不可避免的,这要归功于我们获得的以下不可能结果:对于每个固定的k∈,对于所有恒定度图和查询 o(n^1+1/k) 的平均距离的任何算法的近似因子必须至少为2(k+1)。 这与为<cit.>中的一般有限度量空间设计的算法实现的上限边界相匹配。 因此,在近似保证小于4的恒定度图中的平均距离的任何算法都必须查询Ω(n^2)距离,任何近似保证小于6的算法都必须查询Ω(n^3/2)距离,任何近似保证小于8的算法必须查询Ω(n^4/3)距离,等等,并且还有算法实现这些参数。
我们确切地解决了图形实现,图形刚性和图形全局刚性的复杂性,应用于三种类型的图形:“全局非交叉”图形,这避免了所有配置的交叉;匹配杆图形,具有单位长度边缘并且只考虑非交叉配置;以及具有单位边缘长度的无限制图形(允许交叉)(或全局刚性情况下,边缘长度在{1,2}中)。 我们表明,所有九个问题都是完整的类∃R,由真实世界存在理论或其补充∀R定义;特别是,每个问题都是(co)NP-hard。 这九个结果之一 - 单位距离图的实现是∃R-complete - 以前由Schaefer(2013)显示,但其他八个是新的。 我们加强了以前的几项成果。 火柴杆图实现已知是NP-hard(Eades&Wormald 1990,或Cabello等人)。 2007年),但它在NP的成员资格仍然开放;我们表明它是完整的(可能)更大的类∃R。 已知在{1,2}中具有边缘长度的图形的全局刚性是coNP-hard(Saxe 1979);我们显示它是∀R-complete。 论文的大部分内容都致力于证明肯普的普遍性定理的类似物 - 非正式地,“有一个链接来签署你的名字” - 用于全球非交叉联系。 特别是,我们表明任何多项式曲线 φ(x,y)=0 都可以通过非交叉联动来追踪,从2004年开始解决一个开放的问题。 更一般地说,我们表明,平面中可能通过非交叉联动所追踪的区域恰恰是紧凑的半代数区域(加上整个平面的琐碎情况)。 因此,不因限制非交叉联系而失去任何绘图能力。 我们在火柴杆连接和单位距离连接方面也证明了类似的结果。
闭合准生是多面体表面的闭合曲线,所有点上两面最多180^∘;这种曲线可以直接局部展开。 1949年,Pogorelov证明每个凸多面体至少有三个(非自相交)闭合的准词法,但证明依赖于非建设性的拓扑论证。 我们提出了第一个有限算法,在给定的凸多面体上找到一个闭合的准词位,这是O'Rourke和Wyman在1990年开放问题上的第一个积极进展。 该算法还在对人脸(线段数)的访问总数上建立了伪多项式上限,即O(n L^2/ε^2 l^2)其中n是多面体顶点数,ε是顶点的最小曲率,L是最长边缘的长度,l是顶点与非事件边缘(最小特征大小)之间的最小距离。 在真正的RAM上,算法的运行时间也是伪多项式,即 O(L^2/ε^2 l^2 n n)。 在一个单词RAM上,运行时间增长到O(b^2 Δ^36 L^146/ε^98 l^146 n n · 2^O(|R|)),其中Δ≤n是多面体的最大顶点度,假设多面体的内在几何体是由具有b位整数的恒定大小的激进表达式给出的,并且最多 |R| 是不同的平方根。 在此过程中,我们引入了计算的表达式RAM模型,将过去精确几何计算工作所暗示的真实RAM和单词RAM之间的联系正式化。
假设一个逃跑的玩家(“人类”)在一个区域内部以最高速度1连续移动,而追求的玩家(“僵尸”)以区域外的最大速度r连续移动。 对于什么r可以逃离该地区,即到达边界一个积极的距离追求的玩家,假设双方的最佳发挥? 我们正式确定了这个无限交替的2人游戏的模型,并证明它在任何本地可纠正的区域都有一个独特的赢家。 因此,我们的模型避免了病态行为(玩家都可以有“获胜策略”),这些游戏以前在某些度量空间中为追逐逃避游戏(如狮子和人的问题)确定。 对于某些特定区域,包括等边三角形和正方形,我们给出了关键速度比的确切结果,上面追求的玩家可以赢,并且低于逃跑的玩家可以获胜(以及追求玩家可以获胜)。 对于简单的多边形,我们给出一个简单的公式和多项式时间算法,保证给10.89898-近似临界速度比,我们给出一个伪多项式时间近似方案,用于任意紧密地近似临界速度比。 在消极方面,我们证明了3D中多面体域问题的NP硬度,并证明了对多个逃逸和追求玩家的概括(PSPACE-hardness和NP-hardness甚至近似)的更强结果。
阿基米德的帽子盒定理指出,在球体上均匀测量,以在区间内统一测量。 这一事实可以用来推导出辛普森的规则。 我们介绍了使用 moment maps 作为阿基米德定理的概括的数值立方体公式的各种构造和下界。 我们在简单化上实现了一些众所周知的立方体公式,作为球形设计的投影。 我们结合简单和托利上的立方体公式,在球体上制作新的公式。 特别 S^n 承认一个 7 孵化公式(有时一个 7 种设计)与 O(n^4) 点。 我们使用矩图在简单x上建立PI立方体公式的密度的局部下界。 在此过程中,我们建立了其他独立兴趣的二次和立方的结果。 对于每个 t,我们在 n 尺寸中构建一个带有 O(n^t) 点的格子三角测量(2t+1)-孵化公式。 我们使用向量束导出 Möller 下边界的变体。 我们表明,高斯四边形在正二次公式中是非常局部最优的。
从差异几何角度研究较少的三维流形的八个可能的几何结构中,有以Heisenberg组Heis^3为模型的几何结构。 我们考虑海森堡左不变度量,并使用Levi-Civita连接和曲率张量的一些结果来呈现海森堡组中大地测量线方程的解。 使用“Mathematica”软件包,我们还介绍了海森堡组中大地测量线和公制球的图纸。
我们提出了一种改进数值立方体公式与相等的权重和卷积结构,特别是等重产品公式,使用线性纠错代码。 该建筑在低度下最有效,具有扩展的BCH代码。 使用它,我们获得几个序列的显式,正,内部立方体公式与良好的渐近性每个固定度t作为维度n →∞。 使用间隔的特殊二次公式[arXiv:math.PR/0408360],我们在具有O(n^t/2)点的n-cube上获得一个相等重量的t孵化公式,该公式位于Stroud下限的常数内。 我们还在 n-sphere、n-ball 和 Gaussian ^n 获取 t 孵化公式,当 t 奇数时,具有 O(n^t-2) 点。 当μ是球形对称的,t=5时,我们获得O(n^2)点。 对于每个 t ≥ 4,我们也获得具有 O(n^t-1)点的 n-simplex 的显式、正向的内部公式;对于 t=3,我们获得 O(n) 点。 这些结构无症状地改善了非构造的Tchakaloff绑定。 Victoir最近独立发现了一些相关结果,他还指出,基本结构更直接地使用正交阵列。
考虑所有二元指数多项式f(ξ, η) = ∑_j=1^n p_j(ξ, η) e^2π i (x_jξ+y_jη)的集合E(D, N)，其中多项式p_j ∈ℂ[ξ, η]的次数<D，n≤ N且x_j, y_j ∈𝕋 = ℝ/ℤ。我们找到一个仅依赖于N和D的集合A ⊆ℤ^2，其大小为O(D^2 N log N)，使得f在A上的值能够确定f。注意到A的大小仅比写出f所需参数的数量多一个对数量。我们利用这一结果来证明关于多边形区域的一些唯一性定理，给定其指示函数的傅里叶变换的一小部分样本。如果多边形区域边的不同斜率数量≤ k，则该区域可以从一个预定的傅里叶样本集合中确定，该集合仅依赖于k和最大顶点数N，大小为O(k^2 N log N)。在特别情况下，当所有边都已知平行于坐标轴时，多边形区域可以从一个仅依赖于N且大小为O(N log N)的傅里叶样本集合中确定。我们的方法是非构造性的。
我们引入了一个框架,通过重铸经典球形代码的量子模拟等代码来构建在球体上定义的量子代码。 我们将这个框架应用于玻色子编码,获得猫代码的多模扩展,可以超越以前的构造,同时需要类似类型的开销。 我们基于多顶的猫代码由具有大分离的点集组成,这些点同时形成称为球形设计的平均值集。 我们还重新构建了将带有猫代码的CSS代码作为量子球形代码的连接,揭示了一种自主保护免受降噪的新方法。
我们调查一个正态日志生成函数的凸属性,继续最近对高斯的凸图像的Chen的调查。 我们表明,任何满足其分布函数的“Ehrhard-like”属性的变量都有严格的凸正态log moment生成函数,除非该变量是Gaussian,在这种情况下实现了亲和力。 此外,我们还将满足Ehrhard类属性的变量定性为高斯的凸图像。 作为应用程序,我们在高斯的Rényi差异和强对凹凸变量之间进行了尖锐的比较,并表征了平等案例。 我们还展示了与凸圆锥体相关的圆锥体内在体积序列的基本最佳浓度边界,并且我们获得了McMullen与凸体相关的(欧几里得)内在体积的总和与身体均宽之间的不等式逆转,该宽度概括和磨削了Alonso-Hernandez-Yepe的结果。
继续滚动加载更多
