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

问题在问什么

I’ve just come back from the 48th Annual IEEE Symposium on the Foundations of Computer science , better known as FOCS; this year it was held at Providence, near Brown University. (This conference is also being officially reported on by the blog posts of Nicole Immorlica , Luca Trevisan , and Scott Aaronson .) I was there to give a tutorial on some of the tools used these days in additive combinatorics and graph theory to distinguish structure and randomness. In a previous blo

In the slides, I am tentatively announcing some very recent (and not yet fully written up) work of Ben Green and myself establishing the Gowers inverse conjecture in finite fields in the special case when the function f is a bounded degree polynomial (this is a case which already has some theoretical computer science applications). I hope to expand upon this in a future post. But I will describe here a neat trick I learned at the conference (from the FOCS submission of Bogdan

已知结果和反例

Here is a simple instance of the majority voting trick in action. Suppose one is given a boolean function , where one should think of the number of inputs as being very large. Here of course is the field of two elements. Given any such function, and any shift , one can form its derivative by the formula . (Actually, since has characteristic 2, one could write f(x+h) + f(x) here instead of f(x+h) – f(x), but I will retain the subtraction in order to emphasise the analogy with

Because of this reduction-of-complexity phenomenon, it becomes desirable to represent a function f(x) “efficiently” in terms of its derivatives if at all possible. What do I mean by “efficient”? Well, one has the rather silly representation formula

证明或构造的主线

which allows us to reconstruct the value of f(x) for any x given the value f(0) at 0, and the value of for some h. But this is a very “inefficient” representation, because it will require us to record the derivatives for all h. In applications, we want some representation of f that requires only knowing for a few values of h.

In the case when f is a random function, with all the values of f being independent and uniformly distributed between 0 and 1, this is basically not possible, for the intuitively obvious reason that none of the values of are particularly well correlated to each other, or to f(x). But if f is not random, one can hope to do better. As an example of this, let me mention the following result (a simple instance of a lemma of Bogdanov and Viola):

阅读时建议盯住的点

Lemma . Let be a boolean function, and let . Then at least one of the following statements is true:

This result seems to be rather difficult to prove unless one knows about the majority voting trick, in which case it is rather easy. It works like this. Suppose that f is not pseudorandom; let’s say for sake of argument that it takes the value 1 with probability at least , and the value 0 with probability at most . The key point is then that the functions f and f-1 have significantly different distributions (or histograms ); indeed, f-1 takes 1 with probability at most , and

值得单独记下的条目

• If f is a constant function, then is zero for all h.
• If f is a linear functional , then is constant for all h.
• If f is a quadratic form , then is an (affine-)linear functional for all h.
• More generally, if f is a polynomial in n variables over of degree d, then for every h, is a polynomial of degree d-1. (This is of course totally consistent with one’s experience with differentiation of polynomials in the classical setting.
• (Pseudorandomness) f is unbiased up to error , in the sense that f(x) takes the value 1 for of the possible inputs x (and similarly for the value 0, of course); or
• (Structure) f can be well approximated by a few of its derivatives. More precisely, there exists for some and some boolean function such that for at least of the inputs x.

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

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

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

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

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