The unit distance graph on has edges between those pairs of points at Euclidean distance .\u00a0 The chromatic number of this graph lies between (by exhibiting a small subgraph on vertices with chromatic number ) and (by an explicit colouring based on a hexagonal tiling of the plane).\u00a0 Aubrey de Grey has just posted<\/a> a construction of a unit distance graph with chromatic number , raising the lower bound on by .\u00a0 This MathOverflow post<\/a> is a good jumping off point into the discussion online.<\/p>\n

I was explaining this problem to a colleague and they asked whether this graph was connected (it is) and whether that was still true if we restricted to rational coordinates.\u00a0 It turns out this was addressed by\u00a0Kiran B.Chilakamarri in 1988,<\/a>\u00a0and the answer is the rational unit distance graph is connected from dimension onwards.<\/p>\n

To see that is not connected, consider a general unit vector where is coprime to .\u00a0 Then .<\/p>\n

Claim.<\/strong>\u00a0 is divisible by at most once.<\/p>\n

Proof.<\/em> Squares mod are either , or .\u00a0 If is divisible by then one of the is odd, hence squares to mod .\u00a0 But then cannot be divisible by , which is a contradiction.<\/p>\n

So the entries of in their reduced form do not contain any ‘s in their denominator, and so the same must hold for all sums of unit vectors.\u00a0 Hence we can’t express, say, as a sum of unit vectors, and\u00a0 is not connected to .<\/p>\n

Connectedness in dimension (hence also later) uses Lagrange’s theorem on the sums of four squares.\u00a0 We’ll show that can be expressed as a sum of unit vectors.\u00a0 By Lagrange’s theorem, write .\u00a0 Then<\/p>\n

  <\/span>   <\/span><\/p>\n

hence<\/p>\n

  <\/span>   <\/span><\/p>\n

is a sum of unit vectors.<\/p>\n","protected":false},"excerpt":{"rendered":"

The unit distance graph on has edges between those pairs of points at Euclidean distance .\u00a0 The chromatic number of this graph lies between (by exhibiting a small subgraph on vertices with chromatic number ) and (by an explicit colouring based on a hexagonal tiling of the plane).\u00a0 Aubrey de Grey has just posted a … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[5,17,25,27],"_links":{"self":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/399"}],"collection":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/comments?post=399"}],"version-history":[{"count":0,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/399\/revisions"}],"wp:attachment":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/media?parent=399"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/categories?post=399"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/tags?post=399"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}