陶哲轩博客写数学问题时，通常先把对象定义清楚，再给直觉、反例和证明轮廓。把「(Gil Kalai) The weak epsilon-net problem」改写成可阅读的中文笔记，重点是：问题在问什么、已知到哪一步、下一步最容易走偏在哪。原站广告、分享条和导航已去掉。

问题在问什么

[ This post is authored by Gil Kalai , who has kindly “guest blogged” this week’s “open problem of the week”. – T.]

This is a problem in discrete and convex geometry. It seeks to quantify the intuitively obvious fact that large convex bodies are so “fat” that they cannot avoid “detection” by a small number of observation points. More precisely, we fix a dimension d and make the following definition (introduced by Haussler and Welzl ):

已知结果和反例

For example, in one dimension, if , and where k is the integer part of , then Y is a weak -net for X with respect to convex bodies. Thus we see that even when the original set X is very large, one can create a -net of size as small as . Strong -nets are of importance in computational learning theory , and are fairly well understood via Vapnik-Chervonenkis (or VC) theory ; however, the theory of weak -nets is still not completely satisfactory.

One can ask what happens in higher dimensions, for instance when X is a discrete cube . It is not too hard to cook up -nets of size (by using tools such as Minkowski’s theorem ), but in fact one can create -nets of size as small as simply by taking a random subset of X of this cardinality and observing that “up to errors of “, the total number of essentially different ways a convex body can meet X grows at most polynomially in . (This is a very typical application of the prob

证明或构造的主线

Now consider the situation in which X is now an arbitrary finite set, rather than a discrete cube. More precisely, let be the least number such that every finite set X possesses at least one weak -net for X with respect to convex bodies of cardinality at most . (One can also replace the finite set X with an arbitrary probability measure; the two formulations are equivalent.) Informally, f is the least number of “guards” one needs to place to prevent a convex body from coverin

It is already non-trivial (and somewhat surprising) that is even finite. This fact was first shown by Alon, Bárány, Füredi, and Kleitman (the planar case was achieved earlier by Bárány, Füredi, and Lovász ), who established a bound of the form ; this was later improved to by Chazelle et al . In the other direction, the best lower bound is for some positive c(d); it was shown by Matousek that c(d) grows at least as fast as for some absolute constant c. Furthermore, many of the

阅读时建议盯住的点

The finiteness of was an important ingredient in a paper of Alon and Kleitman which proved a Helly-type conjecture of Debrunner and Hadwiger . Recall that Helly’s theorem asserts that if a finite collection of convex bodies in has the property that any d+1 of them have non-empty intersection, then the whole family has non-empty intersection. Helly’s theorem already easily implies that for . Alon and Kleitman’s theorem asserts that for every integers and , , there is a functio

If we replaced weak -nets by strong -nets then the situation is well understood; the analogue of would be finite if and only if the collection of convex bodies had finite Vapnik-Chervonenkis (or VC) dimension . However, it can be shown that the VC dimension of convex bodies is infinite, and so strong -nets can be required to be arbitrarily large for fixed . One can however use VC theory to show that, for instance, one can find a strong -net for any set with respect to, say, c

值得单独记下的条目

• Problem 1 : For fixed d, what is the correct rate of growth of f as ?
• Problem 2 : Find conditions on the hypergraph H which ensure that is finite. [It is already known that if H has a finite VC dimension D, then is finite, and in fact is bounded by ; the more interesting case is when H has infinite VC dimensi

阅读和落地时建议先做的 5 件事

1. 用自己的语言重写定义和结论，不看原文能不能说清对象是什么。
2. 找一个最小反例或边界情形，确认假设少一条会怎样。
3. 把证明拆成可独立检验的引理，每步只保留一个新想法。
4. 若涉及计算或形式化，先写可复现的小例子，再谈一般情形。
5. 记下尚未解决的缺口：缺估计、缺构造，还是缺正确的范畴。

和智能体、形式化工具怎么接

龙虾PRO做 OpenClaw 落地时，数学笔记最有用的部分往往是「可检验的步骤」：定义、反例、引理边界。智能体适合帮忙展开计算和检索，不适合代替你决定哪条假设能扔。

本文侧重全链路风控方法论。落地时请用自身业务单据做回放验证，不要把示例阈值直接当生产策略。 相关：风控体检 · 方案资源