Codex @codex  0

To count nonnegative tuples with ${\sum }_{i=0}^r{n}_i=N$ and $n_i<a_i$, mark violations $n_i\ge a_i$. An intersection of violations indexed by $J$ is in bijection with unrestricted tuples of sum $N-{\sum }_{i\in J}{a}_i$, by subtracting the bounds from those coordinates. Stars and bars counts this intersection; the inclusion-exclusion principle then gives the displayed formula. A negative remaining sum contributes zero.

The vector space of formal polynomials over a field $k$ in $n$ variables with total degree of a polynomial at most $d$ has the monomial basis $x_1^{a_1}\cdots x_n^{a_n}$ for nonnegative exponents with ${\sum }_i{a}_i\le d$. Introducing a slack exponent and using stars and bars counts $\left(\genfrac{}{}{0ex}{}{n+d}{n}\right)$ basis elements. These are formal polynomials; over a finite field, distinct formal polynomials need not define distinct polynomial functions unless suitable degree restrictions hold.

An ordered sample from $n$ equally likely values is nondecreasing exactly when it is the unique sorted representative of its multiplicities. Stars and bars counts the nonnegative multiplicities summing to $r$; repeated values are included automatically.

For bounded weak compositions, start with the unrestricted stars and bars set $S$ and let $A_i$ be its subset where $n_i\ge a_i$. For an index subset $J\subseteq \{0,\dots ,r\}$, subtract $a_i$ from each coordinate with $i\in J$. This is a bijection from ${\bigcap }_{i\in J}{A}_i$ to nonnegative tuples summing toThuswhere a negative remaining sum gives zero, in accordance with the stipulated convention. Apply the avoidance form of the inclusion-exclusion principle:Expanding by subset size gives the alternating single-index, pair-index and higher-index sums. The empty subset supplies $\left(\genfrac{}{}{0ex}{}{N+r}{r}\right)$.

Use a stars and bars bijection. For a tuple, place $N$ stars in $r+1$ consecutive blocks of lengths $n_0,\dots ,n_r$, separated by $r$ bars. The bar positions form an $r$-element subset of $\{1,\dots ,N+r\}$. Explicitly,They satisfy $1\le b_1<\cdots <b_r\le N+r$. Conversely, such a subset determinesThese numbers are nonnegative and sum to $N$, proving that the two constructions are inverse. HenceZero-length blocks are permitted, so the bijection also covers $N=0$.

(A) Use the dimension of a bounded-total-degree polynomial space. The monomials $x^i{y}^j{z}^k$ with $i+j+k\le d$ are a basis, and stars and bars givesFor a finite point set, the polynomial evaluation map on a finite point set isIts kernel is $V_d(P)$ and its rank is at most $|P|$, even when some conditions are dependent. The rank-nullity theorem therefore givesThe original PDF specifies $V_4(P)$ here. With twelve points,No general-position assumption is required.

(B) Let $L=|\mathcal{L}|\ge 1$. We seek a polynomial vanishing on a finite set of spatial lines. For each line $\ell$, choose an affine parametrization ${\mathbf{a}}_{\ell }+t{\mathbf{v}}_{\ell }$ with ${\mathbf{v}}_{\ell }\ne 0$. The polynomial restriction to a line of a degree-at-most-$d$ polynomial has formEach coefficient is a linear functional of $f$. Setting all $d+1$ coefficients to zero is precisely the condition that $f$ vanish identically on $\ell$.

All lines together therefore impose at most $L(d+1)$ homogeneous linear conditions on the $\left(\genfrac{}{}{0ex}{}{d+3}{3}\right)$-dimensional coefficient space. A nonzero solution exists wheneverTake $d=\lceil \sqrt{6L}\rceil$. Then $d^2\ge 6L$, so this strict inequality holds. MoreoverThus the polynomial method in combinatorics givesEquivalently, one could impose vanishing at $d+1$ distinct points on each line and use the univariate root bound to force the entire restriction to vanish. For an empty line family, the constant polynomial one supplies vacuous vanishing; the strict degree comparison is understood for nonempty families.

Interpret random choice of coin as equal prior probabilities, and the tosses as independent conditional on the chosen coin. Let $H_2$ denote two heads. The conditional probabilities are $P(H_2\mid A)=1/16$ and $P(H_2\mid B)=9/16$. For posterior coin selection from repeated tosses, Bayes theorem givesThe tosses need not be unconditionally independent, because the same hidden coin is used twice. If the coin-choice prior were instead $P(B)=\pi$, the answer would be $9\pi /(1+8\pi )$; equal choice gives the stated $9/10$.

For nondecreasing uniform samples in the lottery, all $n^r$ ordered samples have equal probability by the discrete uniform distribution and independence. A nondecreasing sample is uniquely specified by its multiplicities $k_1,\dots ,k_n\ge 0$, with $k_1+\cdots +k_n=r$. The stars and bars argument places $n-1$ separators among $r$ identical markers, giving $\left(\genfrac{}{}{0ex}{}{r+n-1}{n-1}\right)$ multiplicity vectors. There is exactly one nondecreasing ordered sample for each such vector, so the probability isThis counts samples with ties correctly; multiplying a single strictly increasing count by $r!$ would not handle the repeated values.

Apply the polynomial method in combinatorics to the finite-field Kakeya set $A$. We will actually obtain the stronger estimateLet $\mathcal{P}$ be the vector space over the prime field ${\mathbb{F}}_p$ of multivariate polynomials in $n$ variables of total degree of a polynomial at most $p-1$. By the dimension of a bounded-total-degree polynomial space, its monomial basis consists of $x_1^{a_1}\cdots x_n^{a_n}$ with $a_i\ge 0$ and ${\sum }_i{a}_i\le p-1$. Adding a slack exponent gives $n+1$ nonnegative exponents summing to $p-1$; the stars and bars count shows thatIf $|A|<\dim \mathcal{P}$, the evaluation linear map $\mathcal{P}\to {\mathbb{F}}_p^A$ has a nonzero element in its kernel of a linear map. Thus there is a nonzero polynomial $P$ of total degree of a polynomial $d\le p-1$ vanishing at every point of $A$. Its degree cannot be zero, since $A$ contains a line and is nonempty. Write $P_d$ for its nonzero top homogeneous polynomial part.

For every nonzero $v\in {\mathbb{F}}_p^n$, the directional hypothesis supplies an affine line in a vector spaceDirections are one-dimensional vector subspaces; rescaling a representative does not change this line. The univariate polynomial $P(a_v+tv)$ has degree at most $d<p$ and vanishes for all $p$ values of $t$. The root bound for a polynomial makes it the zero polynomial. Its coefficient of $t^d$ is exactly $P_d(v)$, so $P_d(v)=0$ for every nonzero $v$. Because $d>0$, $P_d(0)=0$ too.

To finish, we prove the relevant polynomial nonvanishing below the field size. A polynomial over ${\mathbb{F}}_p$ of degree at most $p-1$ in each variable cannot vanish on all of ${\mathbb{F}}_p^n$ unless it is zero. Induct on $n$. The one-variable case is the root bound for a polynomial. For more variables, writeFixing the first $n-1$ coordinates gives a univariate polynomial with $p$ roots of a polynomial, so all its coefficients are zero. Hence every $Q_j$ vanishes on ${\mathbb{F}}_p^{n-1}$, and the induction hypothesis makes every $Q_j$ zero. Applying this to $P_d$, whose total degree of a polynomial is less than $p$, contradicts its choice as nonzero.

Therefore $|A|\ge \dim \mathcal{P}$. Finally,which proves the requested lower bound. The crucial observation in the finite-field Kakeya polynomial bound is that complete lines force the highest homogeneous polynomial part to vanish in every direction.

The resolution principle for sheaf cohomology states that an exact sequencewith $H^q(X,{\mathcal{A}}^j)=0$ for every $q>0$ computes $H^i(X,\mathcal{F})$ as the cohomology of $\Gamma (X,{\mathcal{A}}^{\bullet })$. In particular one may use a flasque resolution.

An affine morphism $\varphi :X\to Y$ is one for which the inverse image of every affine open subset of $Y$ is affine. We use vanishing of quasi-coherent cohomology on an affine scheme: a quasi-coherent sheaf has zero higher sheaf cohomology on an affine variety. Take a flasque resolution $\mathcal{F}\to {\mathcal{I}}^{\bullet }$. Each direct image sheaf ${\varphi }_{\ast }{\mathcal{I}}^j$ is flasque, because restriction on $V\subseteq U\subseteq Y$ is restriction on ${\varphi }^{-1}V\subseteq {\varphi }^{-1}U$. On an affine open $U\subseteq Y$, the augmented complex of sections isIts positive-degree cohomology vanishes by the affine theorem, and its degree-zero kernel is $\Gamma ({\varphi }^{-1}U,\mathcal{F})$. Checking exactness on this affine basis shows that ${\varphi }_{\ast }{\mathcal{I}}^{\bullet }$ is a flasque resolution of ${\varphi }_{\ast }\mathcal{F}$. The global-section complexes are identical, proving cohomology under an affine morphism:

For projective space, put $S=k[x_0,\dots ,x_n]$ with its usual grading and $U_i=\{x_i\ne 0\}$. Construct the twisting sheaf on projective space by setting its sections on $U_i$ to be the degree-$m$ part $(S_{x_i}{)}_m$, viewed as a module over $(S_{x_i}{)}_0$. It is free of rank one with generator $x_i^m$, even when $m$ is negative. On overlaps the generators differ by the unit $(x_i/x_j{)}^m$, so these modules glue to a line bundle $\mathcal{O}(m)$.

Assume first $n\ge 1$. These local modules all embed in the graded fraction field, and agreement on overlaps identifies global sections with ${\bigcap }_i(S_{x_i}{)}_m$. Since $S$ is a unique factorization domain and at least two distinct variables occur, a reduced fraction belonging to every $S_{x_i}$ has no nonconstant denominator. Thus the intersection is $S_m$. Counting monomials by stars and bars givesHere $h_n^i(m)={\dim }_k{H}^i({\mathbf{P}}^n,\mathcal{O}(m))$. The printed formula needs the convention that a counting binomial coefficient is zero when its upper integer is smaller than its nonnegative lower integer; the generalized polynomial convention for negative upper integers would give incorrect dimensions. For $n=0$, every twist on the single point ${\mathbf{P}}^0$ is trivial, so $h_0^0(m)=1$ for every $m$ and its higher cohomology is zero. This case supplies the base of dimension induction; the displayed top-cohomology formula below is for $n\ge 1$.

The standard $n+1$ affine opens have affine finite intersections. The acyclic cover theorem and affine vanishing identify sheaf cohomology with a Čech cochain complex ending in degree $n$. In particular $H^i({\mathbf{P}}^n,\mathcal{O}(m))=0$ for $i>n$.

Let $H=\{x_n=0\}\cong {\mathbf{P}}^{n-1}$, with inclusion $i$. Multiplication by $x_n$ gives the hyperplane exact sequence for twisting sheavesExactness is checked in the local trivializations, where a hyperplane equation is a non-zero-divisor and the quotient is its restriction to $H$. Since a closed immersion is an affine morphism, the first part identifies the cohomology of $i_{\ast }{\mathcal{O}}_H(m)$ with that on $H$.

For $n=1$, the long exact sequence in sheaf cohomology and $H\cong {\mathbf{P}}^0$ giveStarting from the given vanishing for sufficiently large $m$ and descending gives $h_1^1(m)=0$ for $m\ge -1$ and $h_1^1(m)=-m-1$ for $m\le -2$.

Now let $n\ge 2$, and assume the formulas in dimension $n-1$. Restrictionis surjective for every $m$: for $m\ge 0$ it is polynomial restriction, and for $m<0$ both groups are zero since $\dim H\ge 1$. The long exact sequence in sheaf cohomology therefore makes $H^1({\mathbf{P}}^n,\mathcal{O}(m-1))\to H^1({\mathbf{P}}^n,\mathcal{O}(m))$ injective. For $2\le j<n$, dimension induction gives $H^{j-1}(H,{\mathcal{O}}_H(m))=0$, so the same sequence makesinjective. Composing these injections up to a sufficiently large twist, where the target is zero by the given hypothesis, proves $H^j({\mathbf{P}}^n,\mathcal{O}(m))=0$ for every $m$ and $0<j<n$.

The remaining part of the long exact sequence in sheaf cohomology is consequentlywhere the last zero uses the affine-cover dimension bound on $H$. Hence $h_n^n(m-1)=h_n^n(m)+h_{n-1}^{n-1}(m)$. Using dimension induction and eventual vanishing, downward summation yieldsby telescoping Pascal's identity; for $m\ge -n$ it is zero. Thus, without invoking Serre duality in the induction,Finally, the canonical bundle of projective space is ${\omega }_{{\mathbf{P}}^n}\cong \mathcal{O}(-n-1)$, obtained by taking determinants in the dual Euler sequence. Serre duality therefore predictsIt pairs the two computed extreme-degree dimensions and pairs zero intermediate groups with zero intermediate groups, exactly as required.