{"id":82,"date":"2008-07-19T13:58:59","date_gmt":"2008-07-19T12:58:59","guid":{"rendered":"https:\/\/wpethzprd.ethz.ch\/kowalski\/2008\/07\/19\/combinatorial-cancellation\/"},"modified":"2024-02-20T13:40:58","modified_gmt":"2024-02-20T11:40:58","slug":"combinatorial-cancellation","status":"publish","type":"post","link":"https:\/\/blogs.ethz.ch\/kowalski\/2008\/07\/19\/combinatorial-cancellation\/","title":{"rendered":"Combinatorial cancellation"},"content":{"rendered":"<p>Here is the example of sums exhibiting a large amount of combinatorial cancellation that I mentioned in a comment on my <a href=\"https:\/\/blogs.ethz.ch\/kowalski\/2008\/07\/07\/is-there-a-combinatorial-square-root-cancellation-philosophy\/\">previous post<\/a>. First, some notation: <em>p<\/em> is a prime number, <em>k<\/em> is a positive integer, and <strong><em>G<\/em><\/strong> is the set of hyperplanes in the vector space <strong><em>F<\/em><\/strong><em><sub>p<\/sub><sup>k<\/sup><\/em> of dimension <em>k<\/em> over the finite field with <em>p<\/em> elements. Then consider<\/p>\n<p>$latex \\sum_{\\emptyset\\not=I\\subset \\mathbf{G}}{\\frac{(-1)^{|I|+1} }{1-p^{j(I)-k}}}$<\/p>\n<p>where, for any subset <em>I<\/em> of <strong><em>G<\/em><\/strong>, we let<\/p>\n<p>$latex j(I)=\\mathrm{dim} \\bigcap_{H\\in I}{H}$<\/p>\n<p>(the dimension of the intersection of the hyperplanes in <em>I<\/em>).<\/p>\n<p>The terms of this sum are of absolute value of size roughly 1, if <em>p<\/em> is large (since <em>I<\/em> is non-empty, the intersection is contained in any of the hyperplanes in <em>I<\/em>, so <em>j(I)&lt;k<\/em>), but there are many of them, namely<\/p>\n<p>$latex 2^{|\\mathbf{G}|}-1=2^{p^k+\\cdots+p+1}-1,$<\/p>\n<p>so one may suspect that the overall sum is quite large.<\/p>\n<p>And yet, it turns out that, for fixed <em>k<\/em> and <em>p<\/em> going to infinity, the sum converges to <em>k. <\/em>My explanation for this is rather indirect, and I will explain it in another post soon, but maybe some readers can see a direct reason?<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Here is the example of sums exhibiting a large amount of combinatorial cancellation that I mentioned in a comment on my previous post. First, some notation: p is a prime number, k is a positive integer, and G is the set of hyperplanes in the vector space Fpk of dimension k over the finite field &hellip; <a href=\"https:\/\/blogs.ethz.ch\/kowalski\/2008\/07\/19\/combinatorial-cancellation\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Combinatorial cancellation<\/span><\/a><\/p>\n","protected":false},"author":625,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-82","post","type-post","status-publish","format-standard","hentry","category-blogroll"],"_links":{"self":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/82","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/users\/625"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/comments?post=82"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/82\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/media?parent=82"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/categories?post=82"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/tags?post=82"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}