There is a genuine qualification missing from the printed bound. With , the family of three singletons has distinct intersections of size zero, which is not congruent to modulo . Nevertheless its size is three, whereas . Thus that bound cannot hold without a restriction on the parameters. The valid prime-power modular intersection bound isIn particular the printed form holds when .
Put with a prime number, and . If , the corrected bound is simply the total number of -sets. Assume henceforth . For an integer , consider the residue detectorFor nonnegative upper arguments, the Lucas theorem and the fact that every base- digit of equals show that is one when and zero otherwise. The assertion also holds for negative upper arguments, using integer-valued generalized binomial coefficients. Indeed the coefficient of in is periodic in the integer exponent modulo : in characteristic , , so multiplying even a formal power series by does not change coefficients of degrees below . Reduce any exponent modulo to obtain the stated detector.
For each , apply that detector to . Its evaluations on form the identity matrix, since the diagonal intersection is and every off-diagonal intersection has a different residue. The detector is represented on Boolean vectors by the multilinear polynomialTo check this expression, evaluate at the characteristic vector of : summing by gives by the coefficient identity for .
Here is the necessary low-degree evaluation rank on a uniform layer, with care about characteristic . Let be the integer incidence matrix whose rows are subsets of size at most , whose columns are all -sets , and whose entries are . Over the rational numbers, for its row satisfiesThus its rational matrix rank is at most . Every larger square minor has integer determinant zero; reducing those determinants modulo gives too. This argument does not divide by a potentially zero element of the finite field. The identity evaluation matrix factors through these incidence rows, so its rank is at most . This proves the qualified bound.
Choose the two-applications alternative. First, the polynomial method in combinatorics yields a constructive lower bound for a diagonal Ramsey number. Let be prime, set , and use all -subsets of as vertices of a complete graph. Color a pair red when its intersection size is modulo , and blue otherwise. A blue clique has size at most by the proved bound with modulus . In a red clique, all distinct intersections belong toFor each vertex of that clique, the polynomial vanishes at all the other vertices' characteristic vectors and is nonzero at its own. Replace repeated powers by on Boolean vectors. Its degree is at most , so the rational version of the same incidence-rank argument bounds a red clique by as well. Therefore this two-coloring has neither color containing a clique of size , andThe usual estimates give and . Thus along this explicit sequence the diagonal Ramsey number exceeds for some absolute . This is substantially larger than any fixed power of .
Second, obtain an exponential lower bound for the chromatic number of Euclidean space. Let , and join two -subsets exactly when their intersection has size . An independent set in this graph avoids that intersection. Among the possible distinct intersection sizes , the only one congruent to modulo is . Hence every independent set has size at most . Embed each vertex as in Euclidean space. Thenso the graph's edges have exactly Euclidean distance one. Each color class must be an independent set, givingThe Stirling formula makes the logarithm of this ratio , where . Since , this is an exponential dimensional lower bound for the chromatic number of Euclidean space. Both applications lie in the valid parameter range of the proved modular bound.
Articles by others on the same topic
There are currently no matching articles.