数学
Mathematics
代数几何
Algebraic Geometry
代数拓扑学
Algebraic Topology
偏微分方程分析
Analysis of PDEs
我们研究了一个4个规则图家族,这些图形是为了测试在一系列不同实数中是否存在组合结构。 我们表明,由Kronecker序列构建的图形可以嵌入到环中,而由二进制van der Corput序列构建的图形可以嵌入到Chamanara表面,在这两种情况下都可以去除一个边缘。 这些结果暗示了序列图的一般理论,该理论可以嵌入到来自区间交换变换的特定翻译表面上。
我们证明,对于每个可计数的字符串图 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的问题。 对于有限字符串图形和平面公制图,我们的证明产生多项式时间(对于字符串图形,这是以输入中给出的表示的大小而言)算法用于生成这种准等距平面图。
我们介绍了一种在三个空间中采样紧密受限的随机等边封闭多边形的算法,该多边形在边缘数中具有运行时线性。 使用共称几何,采样这样的多边形减少到采样一个瞬间多顶,在我们的约束模型中,从组合的角度来看,这种多顶是非常自然的。 这种与组合学的联系产生了我们的快速采样算法和关于顶点到起源的预期距离的显式公式。 我们使用我们的算法来研究密闭多边形的预期总曲率,导致对总曲率的渐近进行了非常精确的猜想。
我们介绍了Design-by-Morphing(DbM),这是一种新颖的设计方法,适用于为2D气翼的拓扑优化创建搜索空间。 大多数设计技术都施加几何约束,有时设计师对设计空间本身产生偏见,从而限制了设计新颖性,只允许进行小的局部变化。 我们表明,DbM方法学对设计空间没有施加任何这样的限制,并允许从搜索空间中推断,从而授予真正激进和大的搜索空间,并带有一些设计参数。 与其他形状设计方法相比,我们应用 DbM 为 2D 气流创建一个搜索空间。 我们优化了这种气翼形状设计空间,以最大限度地提高升降比,CLD_max和失速角度公差,Δα。 使用双目标遗传算法来优化DbM空间,发现我们创建了一个激进气翼的帕累托前部,为这两个目标表现出显着的特性。
我们证明，对于任意固定的(2+1)维复TQFT（无论是Turaev-Viro-Barrett-Westbury型还是Reshetikhin-Turaev型），在闭3-流形上（精确）计算其不变量的问题要么可以在多项式时间内求解，要么从该TQFT的融合范畴构建的某些张量的（精确）收缩是#𝖯-困难的。我们的证明应用了Cai和Chen [J. ACM, 2017]关于复加权约束满足问题的二分结果。我们将重新解释Cai和Chen区分两种情况（即#𝖯-困难的张量收缩与多项式时间不变量）的条件，将其转化为融合范畴的术语，留待未来工作。我们期望通过更多努力，我们的归约可以得到改进，从而直接获得3-流形的TQFT不变量的二分法，而不是针对从TQFT融合范畴构建的更一般的张量。
我们的目标是有一天拍一张结的照片,并有一个电话自动识别它。 在这项解释性工作中,我们解释了一种近似这一目标的策略,使用现代机器学习方法(特别是卷积神经网络和用于图像识别的变压器)和传统算法(计算像琼斯多项式这样的量子不变性)的混合物。 我们提出了简单的基线,直接从图像中预测交叉数,表明即使是轻量级的CNN和变压器架构也可以恢复有意义的结构信息。 长期目标是将这些感知模块与符号重建结合到平面图(PD)代码中,实现下游不变计算,以实现稳健的结分类。 这种两阶段的方法突出了机器学习之间的互补性,机器学习处理嘈杂的视觉数据,以及执行严格的拓扑区分的不变性。
计算三流形拓扑的一个关键结果是,同一三流形的任何两个三角测量都通过有限序列的双星翻转连接,也称为Pachner移动。 这个结果的一个限制是,对于这个序列的结构知之甚少;更多地了解结构可以帮助证明和算法。 受此激励,我们考虑的是“单模态”的动数序列,因为它们分为两部分:第一,单调地增加三角测量大小的序列;第二,单调地减小大小。 我们证明,任何两个相同的三流形的单向三角测量,每个三流形至少有两个四面体,通过2-3和2-0移动的单模态序列连接。 我们还研究了单模态序列的实际效用;具体地说,我们实现了一种算法来找到这样的序列,并使用这种算法来执行一些详细的计算实验。
我们开发了一种在量子低密度奇偶校验(qLDPC)代码中用于容错量子计算的拓扑理论。 我们表明,存在隐藏的简单或CW复杂结构,通过推广Freedman-Hastings代码到流形映射来编码从产品构建中获得的所有qLDPC和CSS代码的拓扑数据。 这是通过从骨骼经典或量子代码的Tanner图形中构建流形来实现的,这些图谱进一步形成了产品歧管和在其三角测量上定义的相关增厚产品代码。 还可以进一步变形将歧管缩回CW复合物,该复合物支持非拓扑代码,并且适用于近期实现的开销最小。 两种类型的代码都承认同源操作,包括可以诱导非Clifford门的杯子产品。 当将此映射应用于从3个副本的良好经典扩展器代码中获得的3D超图产品代码时,我们通过恒定深度电路在具有恒定稳定器重量w=O(1),恒定速率K=Θ(N)和多项式距离D=Ω(N^1/3)的代码上获得非Clifford逻辑CCZ门。 当应用于逻辑CCZ的3D同源产品代码由一对良好的量子和经典的LDPC代码组成时,我们可以进一步提高到D=Ω(√(N))的距离超过Bravyi-König为传统拓扑代码所隐含的N^1/3距离屏障,借助非欧几里得几何。 我们的工作表明,在没有蒸馏过程的情况下,在qLDPC代码上应用本地逻辑非克莱福德门或直接注入高保真魔法状态作为资源(“魔法状态喷泉”)是可行的。 对于同源产品构造,喷泉可以在单轮中同时注入Θ(√(N))魔法状态。
我们证明,通过对定向突变不敏感的链接的n交叉交替链接的检测率在n中呈指数衰减,这意味着它们检测到概率为零的交替链接。 这种现象广泛适用,特别是量子不变性,如Jones或HOMFLYPT多项式。 我们还使用大数据方法来分析几个边缘案例(例如整体Kovanov或HOMFLYPT同源),我们的论点几乎(但不完全)适用,我们提供证据表明它们也表现出相同的渐近行为。
在本文中,我们研究了嵌入f P → Q ×R的存在条件,使f = pr_Q ∘f,其中f P → Q是polyhedra之间的分段线性映射。 我们的重点是图形之间的非退化映射,其中非退行性意味着点的预成像是有限集。 我们引入组合技术,并为一般情况建立必要和充分的条件。 使用这些结果,我们证明提升存在的问题减少了测试3-CNF公式的可满足性。 此外,我们通过 V 构造一个反例给结果。 Poénaru关于将平滑浸入到嵌入。 此外,通过嵌入在所述问题与近似值之间建立连接,我们推断,在从树到段的通用地图的情况下,较弱的条件足以存在提升。
渐近维数是Gromov(1993)引入的度量空间的大尺度不变量。我们证明了每个排除某个图作为胖次式的有界度图的遗传类，其渐近维数最多为2，这是最优的。这一结果在Bonamy、Bousquet、Esperet、Groenland、Liu、Pirot和Scott(J. Eur. Math. Soc. 2023)提出的问题上取得了实质性进展。我们证明的关键是受Baker技术(J. ACM 1994)启发的一个概念。我们说一个图类𝒢具有有界Baker树宽，如果存在一个函数f:ℕ→ℕ，使得对于𝒢中的每个图G，存在G的一个分层，使得由任意连续ℓ层的并集诱导的子图的树宽最多为f(ℓ)。我们证明了每个排除某个图作为诱导次式的有界度图类都具有有界Baker树宽。我们讨论了这一结果在聚类着色和线性时间近似方案设计中的进一步应用。
1907年,亨利·欧内斯特·杜德尼(Henry Ernest Dudeney)提出了一个难题:“将任何等边三角形......剪成尽可能少的碎片,这些碎片将拼合在一起并形成一个完美的正方形”(没有重叠,通过翻译和旋转)。 四个星期后,杜德尼展示了一个美丽的四件套解决方案,今天仍然是最著名的解剖例子。 在本文(一个多世纪后)中,我们终于解决了杜德尼的难题,通过证明等边三角形和正方形没有共同的剖析,有三个或更少的多边形。 我们将问题归结为分析离散图形结构,这些结构代表了形成每个多边形的碎片的边缘和顶点之间的对应关系。
给定一个胞腔嵌入在拓扑曲面S上的加权无向图G，我们描述了计算G中第二短和第三短闭路径的算法，这些闭路径在S中既不同伦平凡，也不同伦于最短的非平凡闭路径或彼此。我们的算法对于第二短路径运行时间为O(n^2log n)，对于第三短路径为O(n^3)。我们还展示了当亏格和边界数量固定时，如何将第二短非同伦平凡闭路径的运行时间减少到O(nlog n)。我们的算法依赖于对S中前三个最短非同伦平凡曲线的配置的仔细分析。作为中间步骤，我们还描述了如何在O(n^2)时间或O(n^3)时间内分别计算S的给定边界分量的一对顶点之间或所有顶点对之间的最短本质弧。
从历史上看,具有N量子比特的量子低密度奇偶校验(LDPC)代码的√(N)log^1/2(N)距离屏障持续了近二十年,直到最近发现了光纤捆绑码。 一个悬而未决的问题是,这种距离障碍是否可以被打破,同时保持执行横向非克利福德门的能力。 在这个方向上,LDPC稳定器代码的另一个长期距离屏障N^1/3 - 自3D颜色代码发现以来存在 - 最近才通过实现Ω(√(N))距离(arXiv:2501.19375)的构造克服。 目前的工作进一步打破了√(N)距离障碍,采用了三个良好的qLDPC代码的同源产物,结合Freedman-Hastings代码到流形映射和三重杯产品来实现横向CCZ门。 生成的代码实现了Ω(N^2/3)距离(Θ(N)的线性X距离)和Θ(N^2/3)的维度,这使得Θ(N^1/3)独立逻辑CCZ魔法状态的容错准备,无需蒸馏(魔法状态喷泉)。 这个新量子代码还激发了一个奇异的3q维流形M家族的发现,它既展示了功率法 Z_2-(q, 2q)-systolic自由,也展示了2q维子歧管的三重交集点。
我们已经开发出一种强化学习代理,通常为高达200个交叉的结图找到最小序列的不注意交叉变化,因此在未标记的数字上给出上限。 我们已经用它来确定57k结的unnotting数。 我们用相反签名的签名,绘制了这些结的关联金额图,其中的总和被覆盖。 该代理人发现了一些例子,其中几个交叉变化在一个不明显的交叉收集导致双曲结。 基于此,我们已经证明,给定的结K和K'满足一些温和的假设,有一个图表,它们的连接和u(K) + u(K') 的通量和未标记的交叉,从而改变其中任何一个会导致一个素数结。 作为副产品,我们获得了260万个不同的硬图的数据集;其中大多数在35个交叉点下。 假设不扣数字的附加性,我们已经确定在最多12个交叉结处的不为人知的不为人知的不为人知的不为人知的不为人知的不为人知的不为人知数的。
代数拓扑中的Peterson hit问题旨在显式确定正次数下商空间Q𝒫_k = 𝔽_2⊗_𝒜𝒫_k的维数，其中𝒫_k表示域𝔽_2上k个变量的多项式代数，被视为Steenrod代数𝒜上的不稳定模。目前解决该问题的方法仍严重依赖手工计算，由于底层计算的复杂性，这些方法极易出错。迄今为止，尚未有任何计算机代数系统中实现的高效算法能系统地解决这个问题。受此启发，在本工作(作为我们项目的第一部分)中，我们首先建立了一个完全基于线性代数的准则，用于判断给定齐次多项式是否为"hit"。据此，我们描述了hit空间的维数。这导致了一种实用可靠的计算方法，在计算机代数系统的支持下，可以确定任意k和正次数下Q𝒫_k的维数。然后我们在SageMath中将所得结果具体实现为新颖算法。作为应用，我们的算法表明Sum和Tai近期工作[15]中关于Q𝒫_5在2^6次数下维数的手工计算结果是不正确的。此外，我们的算法确定(Q𝒫_5)_2^7 = 1985，这落在[15]中估计的1984 ≤(Q𝒫_5)_2^7≤ 1990范围内。
Heegaard 分裂通过将处理方式粘合在一起,为封闭的三流形提供了自然表示。 这些分裂可以等价于两个有限的经络躺在表面,它定义了Heegaard图。 我们提出了一个数据结构,以有效地将Heegaard图表示为正常曲线,相对于通过在二进制中表达正常坐标向量所需的空间测量的复杂表面的三角测量。 这种结构可以明显压缩比三角测量的3个歧管,因为一些家庭获得了指数收益。 即使有了复杂性的简洁定义,我们建立了多项式时间算法,用于比较和操纵图表,执行稳定,检测琐碎的稳定性和减少,以及计算底层流形的拓扑不变性,例如它们的基本和第一个同源组。 我们还将我们技术的早期实现与3个流形的标准软件程序进行了对比,为平均情况实现了更好的精度和更快的算法,并为输入的某些特定演示提供了速度的指数增益。
量子拓扑为定义和计算受量子理论启发的歧管不变性提供了各种框架。 对数学和物理学都很感兴趣的一个这样的框架是Turaev-Viro-Barrett-Westbury状态总和结构,它使用球形融合类别的数据来定义三角三流的拓扑不变性通过张量网络收缩。 在这项工作中,我们分析了来自Tmbara-Yamagami类别的3流形的状态总成不变的计算复杂性。 虽然这些类别是超越有限阿贝尔基(其不变性可以在多项式时间计算)之外状态和不变性的最简单来源,但它们的计算复杂性尚未完全了解。 我们首先确定,即使是最小的TammaRA-Yamagami类别产生的不变性也是#P-硬计算,因此人们期望整个家族也是如此。 然后,我们的主要结果是存在一个固定的参数可操作算法来计算这些3个歧率不变性,其中参数是具有Z/2Z系数的3流形的第一个Betti数字。 与计算拓扑学的其他领域(如表面上的图形)相反,已知3个多孔拓扑中的难题很少,可以采用具有拓扑参数的FPT算法。 然而,这种算法特别感兴趣,因为它们的复杂性仅取决于输入的组合表示,无论大小或组合宽度如何。 此外,在Betti数字的情况下,参数本身在多项式时间中是可计算的。 因此,虽然人们通常期望量子不变性很难经典计算,但我们的结果表明,Tambora-Yamagami类别的计算状态不变的硬度来自经典的三流拓扑,而不是代数输入的量子性质。
低维拓扑中的量子不变性提供了各种各样的有价值的结和3个流形的不变性,由易于计算的显式公式呈现。 它们的计算复杂性已被积极研究,并与拓扑量子计算紧密相连。 在这篇文章中,我们证明,对于Reshetikhin-Turaev模型中的任何3个多孔量子不变性,有一个确定性多项式时间算法,作为输入一个任意闭合的3个多孔M,输出一个具有相同量子不变性的闭合3流形M',这样M'是双曲面,不包含低属嵌入不可压缩的表面,并且由强烈不可还原的Heegaard图呈现。 我们的建筑依赖于Heegaard分裂和Hempel距离的特性。 在计算复杂性的层面上,这证明计算给定的量子不变的3个流形的硬度即使在严格限制输入的拓扑和组合时也能保留。 这积极回答了Samperton提出的问题。
经典的Heawood不等式表示,如果n顶点上的完整图K_n用g手柄嵌入到球体中,那么g ≥(n-3)(n-4)12。 希伍德不等式的一个更高维度的类似物是库内尔猜想。 在简化的形式中,它指出每个整数 k>0 都有 c_k>0,如果 n-simplex 的 k-faces 的联盟嵌入到两个 k 维球体的笛卡尔产品 S^k× S^k 的 g 拷贝的连接总和中,那么 g≥ c_k n^k+1。 对于 k>1 已知只有线性估计。 我们提出了二次估计g≥c_k n^2。 证明是基于几何拓扑,组合学和线性代数之间的美丽和富有成效的相互作用。
继续滚动加载更多
