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

问题在问什么

Van Vu and I have just uploaded to the arXiv our preprint “ On the permanent of random Bernoulli matrices “, submitted to Adv. Math. This paper establishes analogues of some recent results on the determinant of random Bernoulli matrices (matrices in which all entries are either +1 or -1, with equal probability of each), in which the determinant is replaced by the permanent .

More precisely, let M be a random Bernoulli matrix, with n large. Since every row of this matrix has magnitude , it is easy to see (by interpreting the determinant as the signed volume of a parallelopiped) that is at most , with equality being satisfied exactly when M is a Hadamard matrix . In fact, it is known that the determinant has magnitude with probability ; for a more precise result, see my earlier paper with Van . (There is in fact believed to be a central limit theor

已知结果和反例

The permanent looks formally very similar to the determinant, but does not have a geometric interpretation as a signed volume of a parallelopiped and so can only be analysed combinatorially; the main difficulty is to understand the cancellation that can arise from the various signs in the matrix. It can be somewhat larger than the determinant; for instance, the maximum value of for a Bernoulli matrix M is , attaned when M consists entirely of +1’s. Nevertheless, it is not har

In particular, this shows that the probability that the permanent vanishes completely is o(1) (in fact, we get a bound of for some absolute constant ). This result appears to be new (although there is a cute observation of Alon (see e.g. this paper of Wanless for a proof) that if is one less than a power of 2, then every Bernoulli matrix has non-zero permanent). In contrast, the probability that the determinant vanishes completely is conjectured to equal (which is easily seen

证明或构造的主线

Roughly speaking, the strategy is to view the permanent of a Bernoulli matrix recursively as a random signed combination of the permanent of its minors formed from its first n-1 rows, which one can view as the “parents” of the original matrix. The idea is then to take a sort of “genetic” or “evolutionary” viewpoint, and ask how likely the trait of having a large permanent is of being passed from parents to children. The key point is that this trait is “dominant” rather than “

However, there is still a non-negligible chance that there is enough cancellation that a child, even one with many parents with large permanent, may end up having unexpectedly small or vanishing permanent. To avoid these failure probabilities adding up to overwhelm the analysis, we have to exploit some independence. For instance, if , a minor with large permanent will have minors as children. Each child has at least a 1/2 chance of having a permanent as large as that of its p

阅读时建议盯住的点

Just by using the above observations (and crude probabilistic tools such as the union bound and the first moment method), it is already fairly straightforward to show that there exist many minors with large permanent (of size about ) as long as for some . The trickiest part is to manage the last few generations of the evolution, in which we need to get a large number of minors with large permanent (this will imply that the full matrix has large permanent with high probability

Because we were trying to optimise the strength of our result (both in getting the lower bound for the magnitude of the permanent, and getting a reasonable bound on the failure probability), the actual arguments get slightly technical at times. I have uploaded here a very early draft of our paper , in which we prove the weaker result that with probability 1-o(1); the argument here is only a few pages long but already captures many of the key ideas. (This draft was mostly writ

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

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

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

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

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