立方体中的最大内接正方形

zgg___

在9和10层说d(3,7)=2.828427125是不对的。更新d(3,7)=2.892895457。验证代码如下：

1. mm = {{-a, 1/2, -d, -(1/2), -(1/2), -(1/2), -(1/2)}, {1/2, -b, c, -(1/2), -(1/2), -(1/2), -(1/2)}, {c, -b, 1/2, -(1/2), -(1/2), 1/2, 1/2}, {-d, 1/2, -a, -(1/2), -(1/2), 1/2, 1/2}, {-c, b, -(1/2), 1/2, 1/2, -(1/2), -(1/2)}, {d, -(1/2), a, 1/2, 1/2, -(1/2), -(1/2)}, {a, -(1/2), d, 1/2, 1/2, 1/2, 1/2}, {-(1/2), b, -c, 1/2, 1/2, 1/2, 1/2}};
   
2. ll[p1_, p2_] := Dot[p1 - p2, p1 - p2];
   
3. c[x_, y_] := ll[mm[[x]], mm[[y]]];
   
4. e1 = {c[1, 2], c[2, 3], c[3, 4], c[4, 1], c[5, 6], c[6, 7], c[7, 8], c[8, 5], c[1, 5], c[2, 6], c[3, 7], c[4, 8]};
   
5. e2 = {c[1, 6], c[2, 5], c[3, 8], c[4, 7], c[1, 8], c[4, 5], c[2, 7], c[3, 6], c[1, 3], c[2, 4], c[5, 7], c[6, 8]};
   
6. e3 = {c[1, 7], c[2, 8], c[3, 5], c[4, 6]};
   
7. e = Join[Map[# - z &, e1], Map[# - 2 z &, e2], Map[# - 3 z &, e3]];
   
8. ans = Solve[e == 0, {a, b, c, d, z}][[3]];
   
9. ans // N // MatrixForm
   
10. zz = RootReduce[Sqrt[z /. ans]];
    
11. f = First[zz][x]
    
12. N[zz^3, 10]

复制代码

解释一下验证代码吧。其中mm是立方体8个顶点的坐标，每个顶点都是7维的。（mm的构造是通过数值计算手工弄的，因这段时间对优化感兴趣啦）。函数ll和c是求某两点间的距离（其实是距离的平方）。e1、e2、e3分别是计算立方体的边长、面对角线、体对角线（也都是平方啦）。e是这些式子的汇总，其中z是待求的边长的平方。ans是解方程，根据观察取第三组解。f是边长满足的方程。哈哈。

mathe

应该先分析m=2的方法.我们不妨设单位n维立方体的中心在原点，各顶点各坐标分量的绝对值都是$1/2$
假设我们得到最大正方形两个相邻顶点分别为$x=(x_1,x_2,...,x_n),y=(y_1,y_2,...,x_n)$
于是我们可以得出$|x_i|<=1/2,|y_i|<=1/2,S=\sum_{i=1}^n x_i^2=\sum_{i=1}^n y_i^2,\sum_{i=1}^nx_iy_i=0$,我们要求$S$的最大值
采用拉格朗日法可以设目标函数$S=(u+1)\sum_{i=1}^n x_i^2-u\sum_{i=1}^n y_i^2 +v \sum_{i-1}^n x_iy_i$
于是我们有
\(\begin{cases}\frac{\partial S}{\partial x_i}=2(u+1)x_i+v y_i \\\frac{\partial S}{\partial y_i}=-2uy_i+v x_i \end{cases}\)
所以如果对于某个坐标分量，$x_i,y_i$都不取边界条件，那么必然有\(\begin{cases}2(u+1)x_i+v y_i =0\\-2uy_i+v x_i =0\end{cases}\)
等。
很显然对于n是偶数，可以所有$x_i,y_i$都取边界值取到S最大值。
而n是奇数，我们还需要分条件讨论，
比如
$v=0,u!=-1$时
$y_i!=边界 => x_i=0$
$v=0,u!=0$时
$x_i!=边界=>y_i=0$
    上面两者最优情况都对应$x$和$y$都有n-1个坐标取边界，另外一个两者都是0等。。。
而其中都只有一个分量不取边界值，但是是不同分量的情况，必然有这个分量绝对值为1/4

mathe

前面已经分析了v=0的情况，对于奇数n最优结果等于n-1情况
而对于v!=0时，如果u=0,同样有$y_i !=边界 => x_i=0$,最优结果不会好于n-1情况，同样对于u=-1也是一样
所以我们下面可以考虑v!=0,u!=0,u!=-1,而且所有的$x_i!=0,y_i!=0$
于是如果存在某个i使得$x_i,y_i$同时不是边界，那么必然有$-\frac{2(u+1)}{v}=\frac{y_i}{x_i}=\frac{v}{2u}$
所以$-4u(u+1)=v^2$,而且所有这些$\frac{y_i}{x_i}$全部相等。
而如果某个$x_h$不取边界，对应$y_h$取边界，那么必然有$|x_h|=|\frac{v}{4(u+1)}|$
同样如果某个$y_h$不取边界而对应$x_h$取边界，那么必然有$|y_h|=|\frac{v}{4u}|$
记$a=-\frac{v}{2(u+1)},b=\frac{v}{2u}$,
于是我们直到$|x_h|=|\frac{a}{2}|,|y_h|=|\frac{b}{2}|$
而如果$x_i,y_i$同时不是边界时有$\frac{1}{a}=\frac{y_i}{x_i}=b$,所以$ab=1$
不妨设$|b|>=1$,如果$|b|>1$，那么必然这些情况都有$|y_i|>|x_i|$,而由于$y_h$不取边界而$x_h$取边界必然有$|y_h|=|\frac{b}{2}|>\frac{1}{2}$不可能
所以此外最多还有$x_h$不取边界而$y_h$取边界的，对应$|x_h|=|\frac{a}{2}|<\frac{1}{2}=|y_h|$,我们得出它们都是$|x_i|<|y_i|$或$|x_h|<|y_h|$同平方和相等矛盾
所以只能有$|y_i|=|x_i|$的情况，对应$|a|=|b|=1$,而这时如果某个$x_h$不取边界，对应$y_h$取边界，那么必然有$|x_h|=\frac{1}{2}$得出$x_h$也只能是边界，防止对于$y_h$也相同，所以这种情况对应所有的$|x_i|$和对应的$|y_i|$相等。于是问题转化为n个和为0，绝对值不超过$\frac{1}{4}$的数的绝对值和的最大值。在n为奇数时显然不超过${n-1}/4$
所以我们只剩下不存在$x_i,y_i$同时不是边界时的情况。
这种情况对应到$x,y$的内积表达式中各项分别为${x_h}/2,-{x_h}/2,{y_h}/2,-{y_h}/2,1/4,-1/4$.
剩余部分可以用局部调整法来做。
由于对于每个不是边界的$x_i,y_j$,我们可以通过同时调整$x_i,y_i,x_j,y_j$的符号使得$y_i=x_j=1/2$,由此我们总假设$y_i=x_j=1/2$
那么如果现在有三项$x_1,x_2,y_3$都不在边界，我们可以先仅考虑固定其它所有项，仅考虑这三项可以变化的情况，这时我们对应的情况$x_1,x_2,y_3$都只能取$+-{x_h}/2=+-u,+-{y_h}/2=+-v$时应该同时是满足约束$x_1^2+x_2^2-y_3^2=a, x_1+x_2-y_3=b$(其中a,b是常数)的情况下$y_3^2$会取到最大值
记$y=y_3,x=b-x_2$,我们可以消去$x_1$后得到函数$y={a-b^2}/{2x}-x$,其中$y'=-{a-b^2}/{2x^2}-1,y''={a-b^2}/{x^3}$
于是

	x1	x2	y3	a	b	x	a-b^2	y'
u!=v	u	u	v	2u^2-v^2	2u-v	u-v	-(u-v)^2	-0.5
u!=v	u	-u	v	2u^2-v^2	-v	u-v	2u^2-2v^2	(2u)/(v-u)
u=v	u	u	v	0	u	0	0	-1
u=v	u	-u	v	2u^2-v^2	-v	u-v	0	-1

可以知道所有这些情况都还可以局部调整得到更优的结果。所以最终最优结果只可能只有一个$x_i$和一个$y_j$不取边界，也就是它们绝对值取$1/4$其余所有的绝对值都是$1/2$的情况
（需要注意上面有一个u=0时可以取到极值，但是对应某个$x_i=0$得到结果不可能超过n-1的情况，根据情面分析不是最大值）

mathe

对于最大立方体问题。我们假设这个最大立方体一个面上四个顶点为$X(x_1,x_2,...,x_n), Y(y_1,y_2,...,y_n),Z(z_1,...,z_n),W(w_1,...,w_n)$
那么我们首先要求$|x_i|<=1/2,|y_i|<=1/2,|z_i|<=1/2,|w_i|<=1/2$,
以及三条等式约束$||X||^2=||Y||^2=||Z||^2=||W||^2$,要求四个点共球面
另外加约束条件$X+Z=Y+W$,要求四点构成平行四边形，结合上面共球面的条件，四点在平面和球面交集上所以四点共圆又平行四边形，得出四点在一个矩形上。
另外加两条约束$3||X-Y||^2=3||Y-Z||^2=4||X||^2$就可以让它们构成立方体的一个面的四个顶点
也就是总共4n个变量，6条等式约束。这个计算量要比二维的大很多。但是对于给定的n计算机计算应该还好
比较有意思的是，对于n是三的倍数时，我们可以让所有坐标都取到边界点，也就是让$n/3$的分量为为$x_i=1/2,y_i=1/2,z_i=-1/2,w_i=-1/2$,另外$n/3$个分量为$x_i=1/2,y_i=-1/2,z_i=-1/2,w_i=1/2$
余下$n/3$个分量为$x_i=1/2,y_i=1/2,z_i=1/2,w_i=1/2$

mathe

另外一种更加通用的描述形式是设三个相互相邻的面的中心的坐标为$X(x_1,x_2,...,x_n),Y(y_1,y_2,...,y_n),Z(z_1,z_2,...,z_n)$
于是我们要求$\sum x_i^2=\sum y_i^2=\sum z_i^2, \sum x_iy_i = \sum y_iz_i =\sumz_ix_i=0$
以及边界约束条件$|x_i+y_i+z_i|<=1/2,|x_i+y_i-z_i|<=1/2,|x_i-y_i+z_i|<=1/2,|x_i-y_i-z_i|<=1/2$
上面两种方法对于给定的n,计算机都可以使用KKT条件来解决

mathe

14#的形式对于最大正方体更容易分析。这里4n个变量有n+5个等式约束，余下还有3n-5个自由度。朴素的思路是为了让正方体最大，应该让尽量多的坐标取边界值，所以最多还可以取3n-5个，取定后，就可以解方程唯一确定余下n+5个坐标值了。这种选择要求我们尽量多的选择坐标在边界上。
我们查看四个顶点X,Y,Z,W第i个分量$x_i,y_i,z_i,w_i$,如果这四个值中至少有3个取边界值$+-1/2$,那么其中必然有一个对角线上两数都是边界值。
如果$x_i=z_i=1/2$,那么由于$x_i+z_i=y_i+w_i$,那么显然只能$y_i=w_i=1/2$,这种情况对应正方体这个面第i个分量坐标都是$1/2$。（这个高纬情况有点难理解）
而如果$x_i=1/2,z_i=-1/2$,那么$y_i+w_i=0$,所以要么两个点第i个分量取边界，要么4个第i个取边界，只能由形式$1/2,d,-1/2,-d$形式。也就是不可能正好有三个取边界值的情况。
我们再分析4个量中两个取边界的情况，除了上面$1/2,d,-1/2,-d$形式以外，还可以有$1/2,1/2,c,c$的形式,但是不可能有$1/2,-1/2,a,b$形式，因为这种要求$b-a=1$。当然4个量中一个取边界和没有边界总是可以允许的,
其中四个分量都取边界，不使用任何变量，两个分量取边界，分别是$1/2,d,-1/2,-d$和$1/2,1/2,c,c$形式，都只提供一个变量
一个分量取边界，形如$1/2,a,b,1/2+b-a$,提供两个变量，四个分量都不取边界，提供3个变量（使用条件x+z=y+w以后）。
由于除了x+z=y+w的条件后，余下只有5个额外约束，我们总共只能选择5个变量，所以可以有以下几种模式
i)一个纬度上全部不取边界（三个变量），另一个纬度上一个取边界（两个变量），其余所有纬度上全部取边界。
ii)一个纬度上全部不取边界（三个变量），另外两个纬度上都两个取边界（2*1个变量），其余纬度全部取边界。
iii)两个维度上只有一个取边界（2*2个变量），另外一个纬度上两个取边界（1个变量），其余纬度全部取边界。(3#和11#的解在这一类）
iv)一个纬度上只有一个取边界（两个变量），另外三个纬度上两个取边界(3*1个变量），其余纬度全部取边界。
v)五个纬度上两个坐标取边界（5*1个变量），其余纬度全部取边界。（5#的解可以归入这一类）
可以看出，在n很大时，大部分坐标值都可以取边界，最多只有5个纬度有不取边界的值。
然后上面每一种情况，取两个边界的有两种不同模式。而每种简单模式中，变量位置分布也可以有不同的选择位置，所以总体情况数目还是挺多的
如果全部求出，很可能就会找到最优解了。

mathe

比如上面第一类，可以有
$x_1+z_1=y_1+w_1,1/2+z_2=y_2+w_2$
$x_1^2+1/4=y_1^2+y_2^2=z_1^2+z_2^2=w_1^2+w_2^2$
$(x_1-y_1)^2+(1/2-y_2)^2-(y_1-z_1)^2-(y_2-z_2)^2=a$是整数（所以只能是-1,0,1之一）
$3{(x_1-y_1)^2+(1/2-y_2)^2}-4 x_1^2=b$是整数，所以只能取(5,4,3,2,1,0之一）
求解上面方程组可以找出所有维数对应第一类的解。类似其它类会更加复杂。
用https://www.wolframalpha.com/input/ 求解
有合法解(绝对值不超过1/2的实数解)
a=-1,b=0,有解$w_1=0,w_2=-1/2,x_1=0,y_1=0,y_2=1/2,z_1=0,z_2=-1/2$
a=0,b=0,有解$w_1=0,w_2=1/2,x_1=0,y_1=0,y_2=1/2,z_1=0,z_2=1/2$
a=0,b=2, 全部$+-1/2$
a=1,b=3,有解$w_1=0,w_2=1/2,x_1=0,y_1=0,y_2=-1/2,z_1=0,z_2=-1/2$
a=1,b=2, 全部$+-1/2$
除了全部$+-1/2$情况，没有产生其它最优解

mathe

对于一般最大内接m维超立方体情况，设这m维超立方体一个顶点为$A$,和$A$有棱相连接的另外m个顶点依次为$X_1,X_2,...,X_m$
于是$X_1-A+X_2-A+...+X_{m-1}-A=-X_m-A$,我们得出$X_1+X_2+...+X_m=(m-2)A$,这个约束条件对于一般的中心在原点的m维"超平行四边形"都成立。
如果我们在加上这些点都在以原点为球心的某个超球上，也就是它们的范数（到原点距离）都相等，就可以把这个图形改进为m维"超长方形"。
m维图形的超球只需要m+1个点唯一确定，所以这些方程是冗余的，本质上只产生m条方程。
然后我们在加上这m条边相等，于是除了所有$2^m$个顶点坐标绝对值都不超过$1/2$以外，还满足等号约束条件$X_1+X_2+...+X_m=(m-2)A$,$||X_i||^2=||A||^2$以及所有的$||X_i-A||^2=4/m||A||^2$,这里会有一个冗余约束条件。所以本质上，我们可以将变量A直接用${X_1+X_2+...+X_m}/{m-2}$替换，余下2m-1个$X_i$之间的二次约束条件。
由于目标函数$||X_1||^2$只有极小值点，没有极大值，根据https://www.zhihu.com/question/46967237，可以判断出在拉格朗日乘数法限制条件下也只存在极大值，没有最大值。由此除了满足必须的等式约束条件以外，所有其它等式条件都只能在各种不等式边界约束取到。也就是我们需要从$2^m$个顶点绝对值限制条件中挑选出充分多边界条件和2m-1个已知等式限制条件一些起求解即可
另外利用上面条件容易判定如果某个点所有坐标绝对值可以取到1/2，那么n必然是m的倍数

mathe

使用16#的第iii)类，我们可以构造模式：4个前三维坐标依次是
\(\begin{matrix}1/2&a&b&1/2+b-a\\1/2+d-c&1/2&c&d\\f&f&1/2&1/2\end{matrix}\)
于是我们有条件
\(\begin{cases}(1/2+d-c)^2+f^2=a^2+f^2=b^2+c^2=(1/2+b-a)^2+d^2\\(1/2-a)^2+(d-c)^2-(a-b)^2-(1/2-c)^2-(1/2-f)^2=u是整数\\3((1/2-a)^2+(d-c)^2)-4(a^2+f^2)=v是整数\end{cases}\)
显然$-3<=u<=2,-2<=v<=6$
其中$u=0,v=-1$竟然找到一个合法的解$a=0.376963,b=0.302582,c=0.425619,d=0.302582,f=0.361395$
f的最小方程是$256*f^8 - 768*f^6 + 128*f^5 - 96*f^4 + 960*f^3 - 832*f^2 + 600*f - 151=0$
于是对应$n=3k+2$时，我们可以有对应的合法解，这个就是zgg__的方案（昨天我弄错成n=3k+1了)

mathe

对于18#的模型中，我们可以对坐标进行平移，使得外面n维超立方体中离A最近顶点坐标为$(0,0,...,0)$,最远顶点坐标为$(1,1,...,1)$
这时设$A(a_1,a_2,...,a_n), X_h(a_1+t_{h1},a_2+t_{h2},...,a_n+t_{hn})$
于是对于任意i,有$\sum_{h=1}^m t_{hi}=1-2a_i$,以及边界条件$\sum_{\{h|t_{hi}>=0\}}t_{hi}<=1-a_i=\frac{1+\sum_{h=1}^mt_{hi}}2, \sum_{\{h|t_{hi}<=0\}}t_{hi}>=-a_i=\frac{\sum_{h=1}^mt_{hi}-1}2$
或者说$\sum_{\{h|t_{hi}>=0\}}t_{hi}-\sum_{\{h|t_{hi}<=0\}}t_{hi}<=1$,即$\sum_{h=1}^m \abs(t_{hi})<=1$ （取最大值时，这n个不等式应该大部分会变为等式)
以及对于任意h,有$\sum_{i=1}^n t_{hi}^2$都相等（要求等于$1/m\sum_{i=1}^n (1-2a_i)^2=1/m\sum_{i=1}^n (\sum_{h=1}^mt_{hi})^2)$
还有对于任意不同的$h_1,h_2$,有$\sum_{i=1}^n t_{h_1i}t_{h_2i}=0$
而我们的目标是让$\sum_{i=1}^n t_{hi}^2$或$\sum_{i=1}^n (1-2a_i)^2=\sum_{i=1}^n (\sum_{h=1}^mt_{hi})^2$最大化.
为了得到最大值解，我们除了使用${(m+2)(m-1)}/2$组已知的二次等式约束，以及上面n组不等式的部分改为等式的表达式外，另外选择若个独立的$t_{hi}$将它们变为0来求得可能的最优解
我们可以查看$m xx n$阶矩阵
\(T=\begin{pmatrix}t_{11}&t_{12}&...&t_{1n}\\t_{21}&t_{22}&...&t_{2n}\\...&...&...&...\\t_{m1}&t_{m2}&...&t_{mn}\end{pmatrix}\)
于是要求矩阵各行的元素平方和都相同，不同两行之间内积为0（也就是行向量长度都相等而且两两正交）。
而任意一列中数字的绝对值之和不超过1.
得到任意这样的矩阵，我们就可以构造出满足条件的超立方体。而上面构造的目标是使得行向量长度尽量大。
由于最大值必然在所有变量的边界条件取到，所以如果矩阵中一个数字不是0，那么所在列所有非零数字绝对值之和必须为1，由此得出最优解任意一列数字绝对值之和为一。
由此可以得到矩阵中非零数字数目最多是${(m+2)(m-1)}/2+n$个。