P59 · Minimum L2-star discrepancy in the unit hypercube · Discussion

P59 · d = 3, n = 32 · Solver note / 求解记录

邱仲普

P59 d=3, n=32:在 1e-9 网格上用精确坐标下降改进公开构造。比较的是完整清分母整数目标 M·D²,微小改进可能不改变页面的 12 位显示;未证明全局最优。 方法:固定其余坐标时,Warnock 目标关于单个坐标是分段二次函数,分界点为 0、1 和其他点的同维坐标。逐个区间枚举端点及驻点向下、向上取整后的网格点(裁剪到该区间);对每个候选直接计算完整整数目标,只接受严格下降。点、维度均按证书顺序扫描,最多 20 轮;无改进即提前停止,该次搜索完成 2 轮。 精确复现无需重跑搜索:将下面 JSON 作为答案,保留全部小数字符串。 {"points":[["0.331858627","0.066692641","0.650656522"],["0.915991098","0.347943726","0.620729964"],["0.550368408","0.030571445","0.318648809"],["0.352818437","0.947898688","0.523827971"],["0.107908667","0.123547909","0.108497679"],["0.842641535","0.260998828","0.148124782"],["0.393156820","0.318085618","0.207105294"],["0.574110915","0.518165429","0.958467946"],["0.805825619","0.093237421","0.856025586"],["0.169774704","0.493642433","0.272357838"],["0.700014681","0.909173870","0.232026053"],["0.983754594","0.721146306","0.931904175"],["0.726373757","0.164172992","0.504349786"],["0.081072546","0.591439982","0.817354942"],["0.821703319","0.982695396","0.752085172"],["0.594840087","0.699107024","0.597027428"],["0.215549792","0.288025345","0.908391344"],["0.676499240","0.456798246","0.725766427"],["0.248113602","0.231557552","0.413270641"],["0.296294887","0.656520493","0.059215513"],["0.443256672","0.554537836","0.469565750"],["0.413569824","0.882372627","0.871881533"],["0.775047857","0.612729290","0.369965486"],["0.198708216","0.740184635","0.696173276"],["0.958984390","0.532182528","0.245818878"],["0.029121771","0.378420178","0.556971340"],["0.636011153","0.417196964","0.026956503"],["0.752777381","0.820007025","0.989024986"],["0.884505399","0.810334631","0.444939326"],["0.478480209","0.196676012","0.771859256"],["0.502353424","0.778123573","0.166002163"],["0.059275151","0.846450286","0.352609908"]]} 验证:S=10^9,所有坐标 X 为 [0,S] 内整数,恰好 n 行、每行 d 维。D²=3^(−d)−2^(1−d)/n·ΣiΠk(1−xi,k²)+1/n²·Σi,jΠk(1−max(xi,k,xj,k)),M=3^d·2^(d−1)·n²·S^(2d)。一套实现直接计算清分母整数式,另一套用精确有理数计算积分公式后乘 M;两者一致。原整数目标:24576493327366044577564850316345263016373322044954592128;新整数目标:24576493327366044264365283488473742238933097135127706304。