{"id":1363,"date":"2020-12-02T22:22:04","date_gmt":"2020-12-03T03:22:04","guid":{"rendered":"https:\/\/magazine.mcs.cmu.edu\/math\/?page_id=1363"},"modified":"2020-12-18T12:11:17","modified_gmt":"2020-12-18T17:11:17","slug":"discrepancy-and-holes","status":"publish","type":"page","link":"https:\/\/magazine.mcs.cmu.edu\/math\/2020-issue\/discrepancy-and-holes\/","title":{"rendered":"Discrepancy and Holes"},"content":{"rendered":"

[et_pb_section fb_built=”1″ admin_label=”stopthespread” _builder_version=”4.5.2″ background_color=”#878787″ background_color_gradient_direction=”290deg” background_image=”https:\/\/magazine.mcs.cmu.edu\/math\/wp-content\/uploads\/sites\/2\/2020\/12\/feature_bg.png” parallax=”on” parallax_method=”off” custom_padding=”0|0px|0|0px|false|false” box_shadow_style=”preset2″ box_shadow_color=”rgba(0,0,0,0.86)” locked=”off”][et_pb_row column_structure=”1_2,1_2″ _builder_version=”4.5.2″ background_enable_color=”off” custom_padding=”9px||29px|||”][et_pb_column type=”1_2″ _builder_version=”3.14″ custom_padding=”|||” custom_padding__hover=”|||”][et_pb_image src=”https:\/\/magazine.mcs.cmu.edu\/math\/wp-content\/uploads\/sites\/2\/2020\/12\/feature_title.png” alt=”Discrepancy and Holes” title_text=”Discrepancy and Holes” _builder_version=”4.5.2″ _module_preset=”default”][\/et_pb_image][et_pb_text _builder_version=”4.5.2″ text_text_color=”#fff” header_font=”|700|||||||” header_text_color=”#ffffff” header_font_size=”35px” header_2_font=”|600|||||||” header_2_text_color=”#ffffff” header_2_line_height=”1.2em” hover_enabled=”0″ inline_fonts=”Times New Roman”]H<\/span>ow to spread n<\/em> points uniformly in the unit cube \\([0, 1]^d\\)? A natural impulse is to arrange them into a regular grid. For many applications, this is a poor way.<\/p>\n

One such application is numerical integration: given a function f<\/em>, the aim is to compute the definite integral \u222b\\(_{[0,1]^d}\\) f<\/em>. If f<\/em> has a nice antiderivative, we may compute the integral using the Fundamental Theorem of Calculus. Sadly, most functions have no nice antiderivatives and so one must resort to numerical approximations.<\/p>\n

Consider the approximation of \u222b\\(_{[0,1]^d}\\)f<\/em> by a finite sum\u00a0\\(\\frac {1}{n}\\) \u2211p<\/sub><\/em>\u2208P\u00a0 <\/em><\/sub>f<\/em>(p<\/em>), where P<\/em> is an n<\/em>-points set. What happens if P<\/em> is the grid? The good news is that by the very definition of the Riemann integral, the sum converges to the integral as n<\/em> \u2192 \u221e. The bad news is that the convergence is quite slow even for very well-behaved functions.<\/p>\n

For example, for the step function f<\/em>(\\(x_1, . . . , x_d)\\)=1 \\(_{x1\\leq a}\\) the approximation error is proportional to n<\/em>\u22121\/d<\/em><\/sup> for the most values of n<\/em>. This is impractically large even for d = 5. One might be tempted to blame this on the discontinuity in f<\/em>. However even for the function x1<\/sub><\/em>2<\/sup> the error is proportional to n<\/em>\u22122\/d<\/em><\/sup>.<\/p>\n

It turns out that the grid points are a poor choice for our integration method because some axis-parallel boxes contain too few points, whereas others contain too many. Here, by axis-parallel box<\/em> we mean a set of the form B<\/em>=[\\(a_1, b_1\\)) \u00d7 \u00b7 \u00b7 \u00b7 \u00d7 [ad<\/sub><\/em>,bd<\/sub><\/em>), and by too few <\/em>and too many<\/em> we mean that the number of points of P<\/em> that are in B<\/em> deviates significantly from n<\/em> vol(B<\/em>), which is the number of points that we expect to fall into B<\/em> had it been completely uniformly distributed.<\/p>\n

Discrepancy<\/em> of a set B<\/em> is the difference discP<\/sub><\/em>(B<\/em>)=|P\u2229B|\u2212n<\/em> vol(B<\/em>). Discrepancy of P<\/em> is discP<\/em>=max discP<\/sub><\/em>(B<\/em>), where the maximum is over all axis-parallel boxes. For example, discrepancy of the regular grid is \u0398(n<\/em>1\u22121\/s<\/em><\/sup>). Koksma and Hlawka showed that the approximation error for integration of functions of bounded variation is behaves like \\(\\frac {1}{n}\\) <\/em>disc P<\/em> in the worst case. Intuitively, integration with respect to a high-discrepancy set assigns undue weight to some subregions of [0, 1]d<\/sup><\/em> at expense of the others.<\/p>\n

It is a fascinating open problem to find sets of smallest discrepancy in \\([0, 1]^d\\). The best existent constructions have discrepancy of asymptotic order logd<\/sup><\/em>\u22121<\/sup>n<\/em> in dimension d<\/em>. One such construction is the Halton\u2013Hammersley sets. It is easy to define these sets for d<\/em>=2: given a natural number m<\/em> whose base-2 expansion is at<\/sub><\/em> \u00b7 \u00b7 \u00b7 a<\/em>1<\/sub>a<\/em>0<\/sub>, its reversal is the binary number r<\/em>(m<\/em>)=0.a<\/em>0<\/sub>a<\/em>1<\/sub> \u00b7 \u00b7 \u00b7 at<\/sub><\/em>.
\nHalton\u2013Hammersley set is {(m<\/em>\/n<\/em>, r(m)<\/em>) : m<\/em>=0, 1, . . . , n<\/em> \u2212 1}. The higher-dimensional Halton\u2013Hammersley sets are defined similarly using digit reversals of m<\/em> when written in several prime bases.<\/p>\n

Planar Halton\u2013Hammersley sets with n<\/em>=2k<\/sup><\/em> points have a peculiar property: they have zero <\/em>discrepancy on every axis-parallel rectangle of the form [a<\/em>1<\/sub> \/2s<\/sup><\/em> , b<\/em>1<\/sub> \/2s<\/sup><\/em> ) \u00d7 [a<\/em>2<\/sub> \/2t<\/sup><\/em> , b<\/em>2<\/sub> \/2t<\/sup><\/em> ) with s<\/em> + t<\/em> \u2264 k<\/em>. In discrepancy theory, a set with this property is called a net<\/em>.<\/p>\n

In addition to their uses in numerical algorithms, nets are also useful in combinatorial geometry. One such application is to the problem of convex holes. A convex hole<\/em> in a set P \u2282 \u211dd<\/sup><\/em> is a subset H \u2282 P<\/em> that are vertices of a convex polytope; it is called \u2113-hole if |H<\/em>|=\u2113. Erd\u0151s asked if, for every fixed \u2113, all sufficiently large planar sets in general position contain an \u2113-hole. Horton answered Erd\u0151s\u2019s question in negative: he constructed arbitrarily large planar sets without 7-holes. Valtr generalized Horton\u2019s construction to higher dimensions; he showed that there exist arbitrary large sets in \u211dd<\/sup><\/em> without f<\/em>(d<\/em>)-holes for some function f<\/em> that is slightly larger than the factorial. Recently, in a collaboration with Professor Holzman from Haifa, graduate student Ting-Wei Chao and the author showed that the sets of Horton and Valtr are Halton\u2013Hammersley sets in disguise.<\/p>\n

To be precise, Horton\u2019s set is obtained from the planar Halton\u2013Hammersley by stretching y<\/em>-coordinates; the y<\/em>-coordinate 0.a<\/em>0<\/sub>a<\/em>1<\/sub> \u00b7 \u00b7 \u00b7\u00a0 (in binary) becomes a<\/em>0<\/sub> Y<\/em>0<\/sub> + a<\/em>1<\/sub> Y<\/em>1<\/sub> + \u00b7 \u00b7 \u00b7 where Y0 <\/sub>\u226b Y<\/em>1 <\/sub>\u226b \u00b7 \u00b7 \u00b7 is a quickly-decaying sequence of real numbers. A similar transformation turns any net into a set without large holes. Using this relation, new sets in \u211dd<\/sup><\/em> without cd<\/sup><\/em>-holes were found. It is conjectured that the exponential bound is tight but the best lower bound for d<\/em> \u2265 3 is mere 2d<\/em> + 1.<\/p>\n

\u25a0 Boris Bukh
\n<\/em><\/p>\n

[\/et_pb_text][et_pb_button button_url=”https:\/\/www.cmu.edu\/math\/people\/faculty\/bukh.html” url_new_window=”on” button_text=”Boris Bukh’s profile on the Mathematical Sciences’ website” button_alignment=”right” _builder_version=”4.5.2″ _module_preset=”default” custom_button=”on” button_text_size=”13px” button_text_color=”#e0e0e0″ button_bg_color=”#00687f” button_border_width=”0px” button_border_radius=”0px” button_font=”|700|||||||” box_shadow_style=”preset4″][\/et_pb_button][\/et_pb_column][et_pb_column type=”1_2″ _builder_version=”3.14″ custom_padding=”|||” custom_padding__hover=”|||”][et_pb_image src=”https:\/\/magazine.mcs.cmu.edu\/math\/wp-content\/uploads\/sites\/2\/2020\/12\/feature_Figure1_White.png” alt=”Figure 1: Discrepancy of a box is the difference between the expected and the actual number of points inside.” title_text=”Figure 1: Discrepancy of a box is the difference between the expected and the actual number of points inside.” _builder_version=”4.5.2″ _module_preset=”default”][\/et_pb_image][et_pb_text _builder_version=”4.5.2″ _module_preset=”default” text_font=”|700|on||||||” text_text_color=”#ffffff” text_font_size=”11px” custom_margin=”-73px||80px||false|false”]<\/p>\n

Figure 1: Discrepancy of a box is the difference between the expected and the actual number of points inside.<\/p>\n

[\/et_pb_text][et_pb_image src=”https:\/\/magazine.mcs.cmu.edu\/math\/wp-content\/uploads\/sites\/2\/2020\/12\/feature_Figure2_White.png” alt=”Figure 2: Halton-Hammersley set of size 16. The number of points in every not-too-small dyadic rectangle is exactly proportional to its area.” title_text=”Figure 2: Halton-Hammersley set of size 16. The number of points in every not-too-small dyadic rectangle is exactly proportional to its area.” _builder_version=”4.5.2″ _module_preset=”default”][\/et_pb_image][et_pb_text _builder_version=”4.5.2″ _module_preset=”default” text_font=”|700|on||||||” text_text_color=”#ffffff” text_font_size=”11px” custom_margin=”-73px||101px||false|false”]<\/p>\n

Figure 2: Halton-Hammersley set of size 16. The number of points in every not-too-small dyadic rectangle is exactly proportional to its area.<\/p>\n

[\/et_pb_text][et_pb_image src=”https:\/\/magazine.mcs.cmu.edu\/math\/wp-content\/uploads\/sites\/2\/2020\/12\/feature_Figure3_White.png” alt=”Figure 3: A 5-hole in a planar set.” title_text=”Figure 3: A 5-hole in a planar set.” _builder_version=”4.5.2″ _module_preset=”default”][\/et_pb_image][et_pb_text _builder_version=”4.5.2″ _module_preset=”default” text_font=”|700|on||||||” text_text_color=”#ffffff” text_font_size=”11px”]<\/p>\n

Figure 3: A 5-hole in a planar set.<\/p>\n

[\/et_pb_text][\/et_pb_column][\/et_pb_row][\/et_pb_section][et_pb_section fb_built=”1″ _builder_version=”3.22″ background_color=”#e0e0e0″ custom_margin=”0px|||||” custom_padding=”30px|0px|30px|0px|false|false” locked=”off”][et_pb_row column_structure=”1_2,1_2″ _builder_version=”3.25″ custom_padding=”0|0px|0|0px|false|false”][et_pb_column type=”1_2″ _builder_version=”3.25″ custom_padding=”|||” custom_padding__hover=”|||”][et_pb_button button_url=”\/math\/2020-issue\/research-roundup-2\/” button_text=”Research Roundup, Pt 2″ _builder_version=”4.5.2″ custom_button=”on” button_text_color=”#00687f” button_border_width=”0px” button_font=”||||||||” button_icon=”%%2%%” button_icon_color=”#00687f” button_icon_placement=”left” button_on_hover=”off” button_text_size__hover_enabled=”off” button_one_text_size__hover_enabled=”off” button_two_text_size__hover_enabled=”off” button_text_color__hover_enabled=”off” button_one_text_color__hover_enabled=”off” button_two_text_color__hover_enabled=”off” button_border_width__hover_enabled=”off” button_one_border_width__hover_enabled=”off” button_two_border_width__hover_enabled=”off” button_border_color__hover_enabled=”off” button_one_border_color__hover_enabled=”off” button_two_border_color__hover_enabled=”off” button_border_radius__hover_enabled=”off” button_one_border_radius__hover_enabled=”off” button_two_border_radius__hover_enabled=”off” button_letter_spacing__hover_enabled=”off” button_one_letter_spacing__hover_enabled=”off” button_two_letter_spacing__hover_enabled=”off” button_bg_color__hover_enabled=”off” button_one_bg_color__hover_enabled=”off” button_two_bg_color__hover_enabled=”off”][\/et_pb_button][\/et_pb_column][et_pb_column type=”1_2″ _builder_version=”3.25″ custom_padding=”|||” custom_padding__hover=”|||”][et_pb_button button_url=”\/math\/2020-issue\/alumni-news\/” button_text=”Alumni News” button_alignment=”right” _builder_version=”4.5.2″ custom_button=”on” button_text_color=”#00687f” button_border_width=”0px” button_font=”||||||||” button_icon=”%%3%%” button_icon_color=”#00687f” button_on_hover=”off” button_text_size__hover_enabled=”off” button_one_text_size__hover_enabled=”off” button_two_text_size__hover_enabled=”off” button_text_color__hover_enabled=”off” button_one_text_color__hover_enabled=”off” button_two_text_color__hover_enabled=”off” button_border_width__hover_enabled=”off” button_one_border_width__hover_enabled=”off” button_two_border_width__hover_enabled=”off” button_border_color__hover_enabled=”off” button_one_border_color__hover_enabled=”off” button_two_border_color__hover_enabled=”off” button_border_radius__hover_enabled=”off” button_one_border_radius__hover_enabled=”off” button_two_border_radius__hover_enabled=”off” button_letter_spacing__hover_enabled=”off” button_one_letter_spacing__hover_enabled=”off” button_two_letter_spacing__hover_enabled=”off” button_bg_color__hover_enabled=”off” button_one_bg_color__hover_enabled=”off” button_two_bg_color__hover_enabled=”off”][\/et_pb_button][\/et_pb_column][\/et_pb_row][\/et_pb_section]<\/p>\n","protected":false},"excerpt":{"rendered":"

How to spread n points uniformly in the unit cube \\([0, 1]^d\\)? A natural impulse is to arrange them into a regular grid. For many applications, this is a poor way. One such application is numerical integration: given a function f, the aim is to compute the definite integral \u222b\\(_{[0,1]^d}\\) f. If f has a […]<\/p>\n","protected":false},"author":4,"featured_media":0,"parent":1156,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_et_pb_use_builder":"on","_et_pb_old_content":"","_et_gb_content_width":"","footnotes":""},"class_list":["post-1363","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/pages\/1363","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/comments?post=1363"}],"version-history":[{"count":38,"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/pages\/1363\/revisions"}],"predecessor-version":[{"id":1710,"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/pages\/1363\/revisions\/1710"}],"up":[{"embeddable":true,"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/pages\/1156"}],"wp:attachment":[{"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/media?parent=1363"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}