Skip to content

Latest commit

 

History

17 Commits

Folders and files

NameName
Last commit message
Last commit date
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Covering System

这是覆盖系统的交互式 Visualization 项目。首页现在并列提供两个实验空间:

  • tree.html:树形覆盖,把文章中的前缀表达式直接解析成可拖动的树。
  • game.html:矩形覆盖,可读取同一套前缀表达式或原有坐标编码。

树形覆盖的输入由 01_主线/形式化验证/code/covering.hpp 编译成的 WebAssembly 直接解析。网页不再维护一套独立的正式语法;cpp/parser_bridge.cpp 只负责把 C++ AST 无损地转换成页面使用的 JSON,不修改验证器。01 分别画成白色与黑色圆叶子,普通树节点只保留分叉线,递归树的最后一支以加粗箭头收尾。

在本目录运行:

node server.js

然后访问 http://127.0.0.1:4173/tree.html。树形覆盖与矩形覆盖运行时都调用这个 WebAssembly 解析器;包括 5^\uparrow(...)、Unicode 5↑(...)p_w↑Ap↑_wA 在内的输入都走同一个 C++ Parser。修改 covering.hpp 后运行 cpp/build-wasm.ps1 重建浏览器模块。

tree/syntax-contract.json 是网页解析器与 covering.hpp 的共享样例契约。运行 node tree/parser.test.js 检查网页语义;运行 node tree/parser.sync.test.js 会临时编译一个很薄的 C++ 探针,并把两套解析器对同一批输入的接受行为与公共归一形逐项比较。以后修改符号时,先改这份契约,任一实现未同步都会直接报错。

问题

覆盖系统是由 P. Erdos [1] 的1950年论文中首次引入的。覆盖系统是一个模数大于 $1$ 且互不相同的同余类的有限集合,使得每个整数至少属于其中一个类。在同年发表的同一篇论文中,Erdos 写道:“很可能对于每个 $c$,都存在一个所有模数均为 $>c$ 的系统。”这一陈述被称为最小模数问题,而这个问题在 Bob Hough [2],以否定的方式解决之前,花费了六十多年时间。他获得了最小模数 $10^{16}$ 的上界。

虽然现在已知覆盖系统的最小模数不能任意大,但最小模数可以有多大仍是一个问题。迄今为止最好的结果是 Tyler Owens [3],构造了一个模数 $42$ 的覆盖系统,他基于的是 Pace Nielsen [4] 的思想和方法。

符号说明

  • 简记剩余类 $a\pmod n$$a+n\mathbb{Z}$$n_a$
    特别的 $1=\mathbb{Z}$,$0=\varnothing$。
  • 再简记集合运算 $A\cup B=A+B$,$A\cap B=AB$。

由于中国剩余定理,我们可以分解剩余类为若干素数幂的剩余类:
$$ \begin{aligned} n&=\prod_{i=1}^kp_i^{n_i}\ \to n_a&=\prod_{i=1}^k(p_i^{n_i}){a}=\prod{i=1}^k(p_i^{n_i})_{a\bmod p_i^{n_i}} \end{aligned} $$

例如 $12_{11}=3_24_3$,再利用分配律即可得到: $$ \begin{aligned} &12_{11}+3_0\ =&3_24_3+3_01\ =&3(_24_3+_01)\ =&3(_24_3+_01+_10)\ =&3(1,0,4_3)\ \end{aligned} $$

这里 $(1,0,4_3)$ 表示模 $3$ 的三个剩余类:余 $0$ 类取全集,余 $1$ 类取空集,余 $2$ 类取 $4_3$

注意到 $4_1+4_3=2_1$,于是定义 $4_1=2_12_0$,$4_3=2_12_1$。
更一般的,我们定义同质数的幂的乘积不是交集,而是: $$ \begin{aligned} (p^{n_1}){a_1}(p^{n_2}){a_2}&=(p^{n_1+n_2}){a_1+a_2}=p^{n_1+n_2}{a_1+a_2}\ \to p_{a_1}p_{a_2}\dots p_{a_n}&=p^n_{a_1+a_2p+\dots+a_np^{n-1}} \end{aligned} $$

以此类推,我们可以得到:

$$ \begin{aligned} &12_{11}+9_5+6_2+3_0\\ =&3(1,0,3(0,1,0)+2(1,2(0,1)))\\ =&3(1,0,3_1+2(1,2_1)) \end{aligned} $$

这个符号是 Nielsen [4] 符号的一种变体,目的是更紧凑地表示覆盖系统。


对于 $q\perp p$,有: $$p(A)=q(p(A),p(A),\dots,p(A))$$

于是我们还可以形式化的做验证,例如最小模数等于 $2$ 的一个构造是: $$2(1,2_0)+3(1,2_1,4_3)$$

我们可以不断分配+合并来验证这是一个覆盖: $$ \begin{aligned} &2(1,2_0)+3(1,2_1,4_3)\ =&3(1+2(1,2_0),2_1+2(1,2_0),2_12_1+2(1,2_0))\ =&3(1,2(1,1+2_0),2(1,2(1,1)))\ =&3(1,2(1,1),2(1,1))\ =&3(1,1,1)=1\ \end{aligned} $$

然后再利用分配率+中国剩余定理可以得到具体的剩余类: $$ \begin{aligned} &2(1,2_0)+3(1,2_1,4_3)\ =&2_0+2_12_0+3_0+3_12_1+3_24_3\ =&2_0+4_1+3_0+6_1+12_{11} \end{aligned} $$

然而大部分情况下我们都没必要合并为具体的剩余类,
只需要检验是否有相同的模数即可。

按照这个形式化方法,读者可以自行验证最小模数等于 $3$ 的一个构造: $$2(2(1,2_0),8_0)+3(0,2(4_3,1),4_2+3(1,2_1,2(0,2(0,2(1,2(1,2(0,1)))))))$$

最小模数等于 $4$ 的一个构造:


对于一个中缀表达式的森林: $$2(1,2(1,0))+3(1,2(0,1),2(0,2(0,1)))$$ 我们可以写成 $$2_0+2_12_0+3_0+3_12_1+3_22_12_1$$


[1] P. Erdos. On integers of the form 2^k + p and some related problems. Summa Brasil. Math., 2:113123, 1950.
[2] Bob Hough. Solution of the minimum modulus problem for covering systems. Ann. of Math. (2), 181(1):361382, 2015.
[3] Owens, Tyler E.. “A Covering System with Minimum Modulus 42.” (2014).
[4] Pace P. Nielsen. A covering system whose smallest modulus is 40. J. Number Theory, 129(3):640666, 2009

About

我关于 erdos 覆盖问题的相关研究,会有一些观点,还有一些可视化小玩意

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages