Talk:Lonely runner conjecture

Only positive speeds needed in reduced case?

Reducing the problem from k+1 runners to k runner by assuming that one of the runner has speed zero imposes on the first spot that some runners may have negative speeds. It is stated that one can restrict to the case of k "positive integers" as proven in the paper of Bohman, Holzman, Kleitman. I cannot see the argument why it is possible to restrict to positive (integer) speeds nor can I find this argument for positivity in Bohman, Holzman, Kleitman. To clarify, the argument why one can restrict to rational (hence integer) speeds is contained in the mentioned paper. — Preceding unsigned comment added by 134.147.253.243 (talk) 15:32, 20 November 2018 (UTC)

Adding the same speed to every runner doesn't change the situation. If there is a solution with any integers there is also one with one runner at speed 0 and other runners at positive speed and vice versa. --mfb (talk) 06:56, 21 November 2018 (UTC)

Known results

The table with known results, and the year when they were proved, contradict the dates cited on the page at the Open Problem Garden. In any case, the table needs inline citations. Hermel (talk) 10:17, 20 March 2009 (UTC)

I'm working on correcting the table with citations and adding k+1 = 7. This will take a few days, so please bear with me. Gramby (talk) 21:03, 19 April 2011 (UTC)

Thanks a lot for your effort. Hermel (talk) 16:57, 22 April 2011 (UTC)

Trivial results

The results for k <= 3 should be added, at least in the "Known results" box. For k = 0 and 1 the result is trivial (t=0 and t=v2-v1), and I can add it myself, but k = 2 could have its own explanatory section. MestreLion (talk) 15:41, 28 February 2013 (UTC)

k+1?

Not substituting k+1 for k is just stupid. I'm changing that shit.

k=3?

Why is it that any proof for k larger than 3, automatically proves it for k=3? - DPizzo (talk) 23:22, 21 August 2013 (UTC) Just add runner speed infinitesimally small. It is trivial. — Preceding unsigned comment added by Mtheorylord (talk • contribs) 02:06, 11 August 2016 (UTC)

The distance goes up with k=3 compared to larger numbers. But it is easy to proof directly: Consider speeds relative to runner A, let runner C be faster than B. If the speed of C does not exceed twice the speed of B, then A will be lonely within the first round of both, otherwise A will lonely within the first round of B and the nth round of C. --mfb (talk) 17:51, 13 November 2016 (UTC)

animation/gif

what are the speeds for each of the runners in the gif animation to the right? — Preceding unsigned comment added by 69.171.166.1 (talk) 22:32, 8 September 2013 (UTC)

Non-rational values

With respect to this: it is a true statement. Its truth is the underlying reason that this article begins "in number theory". But (1) it is uncited, and (2) it is certainly not part of the formulation of the problem (which is the topic of the section to which it was added). With a citation, we could certainly try to fit it in somewhere else. --JBL (talk) 00:41, 1 November 2021 (UTC)

GA Review

This review is transcluded from Talk:Lonely runner conjecture/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: David Eppstein (talk · contribs) 01:23, 22 May 2022 (UTC)

I have edited the article, but they were very minor edits, long ago, so I am not a significant contributor.

GA review – see WP:WIAGA for criteria

1. Is it well written?

   A. The prose is clear and concise, and the spelling and grammar are correct:

   This is the biggest area where I think significant improvement can still be made. The article is on a technical topic, so one should not expect all of it to be readable by a non-mathematical audience. However, I think it should be possible to make the summaries of the problem and of its application to visibility readable to interested amateurs, and the rest of the article readable to undergraduate mathematics students. Instead, much of the article remains written in technical language aimed at specialists, rather than following WP:ONEDOWN. Some of the points I found confusing, or overly technical, include:

   • Lead sentence: Most papers on this topic appear to be classified by MathSciNet as Diophantine approximation, more specifically than number theory. Should this topic be mentioned in the lead?

   I think so. In most sources which focus exclusively on it it's treated as a sort of "simultaneous Diophantine approximation" problem. Done. Ovinus (talk) 19:04, 22 May 2022 (UTC)

   • In the formulation, it might be helpful to clarify that negative speeds are allowed (and are necessary for the equivalence to the version with one stationary runner).

   Yes, this is not obvious, great. Ovinus (talk) 19:04, 22 May 2022 (UTC)

   • "Proving the result for any stationary runner implies the general result for any runner, since they can be made the stationary runner.": This is one of the points that I think will be obvious to some but can be spelled out to be clearer than others. It might help to point out that adding or subtracting the same value to all runners' speeds does not affect their relative positions, so we can choose what to subtract to make any runner's speed zero.

   Done Ovinus (talk) 19:04, 22 May 2022 (UTC)

   • I think too much of the displayed equation is written in shorthand mathematical notation that would be better spelled out, and that inequality notation is clearer than interval membership notation: "there exists a time $t>0$ such that, for all $v_{i}$, ${\tfrac {1}{n}}\leq \operatorname {frac} (v_{i})\leq 1-{\tfrac {1}{n}}$." Also, your notation for the fractional part is not a good choice; despite the later explanation, it took me a long time to figure out that you were not trying to describe a set of numbers and trying to understand what you meant by asking for a set to be an element of an interval.

   Will keep this in mind as I continue. Replaced the fractional part with your suggestion. Ovinus (talk) 19:04, 22 May 2022 (UTC)

   • "part of his work in Diophantine approximation": this is only meaningful to people who already know what Diophantine approximation is, or are willing to click on the link. What is Diophantine approximation? How do lonely runners fit into that topic?

   Done. Ovinus (talk) 19:04, 22 May 2022 (UTC)

   • "Suppose C is a closed body... half-integer coordinates": long and kind of awkward. Can we split this up?
   • "asks for the minimum α for which": but alpha was already chosen to be some particular unspecified given value. Now it's not given, but must be optimized over. Again, awkward.
   • "if C is a unit n-hypercube": if it was always going to be a hypercube centered at the origin, why was it described much more generally as a convex body containing the origin two sentences earlier? What is the point in asking readers to reconcile these two somewhat technical specifications? Also the n is not consistently formatted with the rest.

   That's a fair point, esp. since Cusick makes no claims regarding other shapes. Recast much of this paragraph. Ovinus (talk) 19:04, 22 May 2022 (UTC)

   • "then the solution is": I take it this means alpha? I think this could all be phrased more clearly by starting with the hypercubes and the solution, and omitting the generalization to convex sets and optimization of alpha. The lonely runner conjecture implies that hypercubes of side length (n-1)/(n+1), centered at half-integer points, block all visibility from the origin.
   • Similarly, why do we need a name lambda(n) for the function (n-1)/(n+1)? Why do we need that name in the caption of the figure? Just use 1/3 in the figure and (n-1)/(n+1) for the solution.

   Done above. Ovinus (talk) 19:04, 22 May 2022 (UTC)

   • Is a "vertex set" supposed to be something different from a set? Is the notation G(Z,D) ever used after you define it? Wouldn't D={1} be a more natural example to start with? But in general I find this whole paragraph very confusing. If gcd(D)=g≠1 then G(Z,D) is just g disjoint copies of G(Z,D/g) and has the same chromatic number, so why is the assumption about the gcd needed? And the first displayed equation of the reference states that the chromatic number is at most |D|+1 unconditionally, so why is the lonely runner conjecture relevant? The reference does not even mention lonely runners.

   Yup, I bungled this one. Fixed, although it's fairly technical now. (It's from [1] page 5688) Let me know if/how I can make the explanation more palatable. I don't think that $\{1\}$ is the best initial example as it may mislead the reader into thinking the resulting graph only has one component, but lmk if you disagree. Ovinus (talk) 19:04, 22 May 2022 (UTC)

   • The nowhere zero flow paragraph is similarly nonsensical. If f attains at most k different values, then multiplying all flow values by a large integer produces another integer nowhere-zero flow that attains at most k different values, none of which are in the stated set {1,2,...k}. Please clarify.

   Fixed. Ovinus (talk) 19:04, 22 May 2022 (UTC)

   • I found the definition of delta confusing. It is the largest value for which all runners in all systems of runners have loneliness at most delta. Stating "the upper bound delta=1/n is sharp" is also confusing way of saying "delta ≤ 1/n".

   Indeed it's a bit confusing. Tried to recast a bit. Ovinus (talk) 19:04, 22 May 2022 (UTC)

   • "If the lonely runner is fixed": were they in need of repair? Did you mean "If the lonely runner has speed zero" or something else?

   Hahaha. Hope he's okay. Done. Ovinus (talk) 19:04, 22 May 2022 (UTC)

   • In the "under specific assumptions" paragraph, what is i? Did you mean to quantify universally over all i?

   Done. Ovinus (talk) 19:04, 22 May 2022 (UTC)

   • In the "sporadic examples" paragraph, I don't like the unexplained notation $s(1,3,4,7)$, and the equality between $v_{i}$ (for some unspecified $i$) and whatever this notation is supposed to mean. Anyway it's incorrect because one could also permute the speeds and get a different assignment to each v_i. I think it would be clearer to say something about "up to scaling" and then specify the set of nonzero speeds as {1,3,4,7}, without saying anything about v_i. Just say that's the set of speeds. We don't need to know which one of them goes with which index. And using sets in this way automatically avoids complications with permutations.

   Great thinking, done. Ovinus (talk) 19:04, 22 May 2022 (UTC)

   • In the "Other results" section, now delta means something different than it did before, a random variable depending somehow on the choice of speeds rather than a number depending only on n and determined from the worst combination of speeds. But we are not told how it depends on the speeds. Are we setting one speed zero and looking at the gap of that one runner? Are we looking at all runners from a given instance and choosing the one with the smallest gap? Does it make a difference?

   I don't think it ultimately matters in the limit, but the source uses the "fix one runner" convention, so done. I also used $\delta$ in this somewhat generic way at the beginning of this section and distinguished it from $\delta _{n}$. Let me know if that looks weird, and if so I could use a notation like $\delta _{S}$ or something, where S is a set of numbers. Ovinus (talk) 19:04, 22 May 2022 (UTC)

   B. It complies with the manual of style guidelines for lead sections, layout, words to watch, fiction, and list incorporation:

   No issues with section layout. Most of the lead appropriately summarizes body content. But the history ("first posed by Wills") appears to be a claim appearing only in the lead; shouldn't there be somewhere in the body that this summarizes, maybe with a source by someone else crediting Wills rather than Wills' own work as its own source. Also I think usually Cusick is given some credit, despite being a little later.

   Done to both. Ovinus (talk) 19:04, 22 May 2022 (UTC)

2. Is it verifiable with no original research?

   A. It contains a list of all references (sources of information), presented in accordance with the layout style guideline:

   I would have made some different style choices in the citations (in particular, adding author-link parameters for notable authors and omitting redlinks for non-notable journals) but the formatting appears very consistent and thought-out.

   Added author links anyway. Ovinus (talk) 19:04, 22 May 2022 (UTC)

   B. All in-line citations are from reliable sources, including those for direct quotations, statistics, published opinion, counter-intuitive or controversial statements that are challenged or likely to be challenged, and contentious material relating to living persons—science-based articles should follow the scientific citation guidelines:

   The sources are mainly primary rather than secondary, but I think that's ok for this sort of topic. All appear to be properly peer-reviewed articles in mainstream mathematics journals.

   C. It contains no original research:

   All claims are properly cited to sources, either in footnotes inline parenthetical citations. Spot-checking found matching statements in the sources.

   D. It contains no copyright violations nor plagiarism:

   Earwig spotted only copied titles of references. No problematic copying.

3. Is it broad in its coverage?

   A. It addresses the main aspects of the topic:

   There are more publications on this problem than are cited here, but I didn't spot anything essential that was missed, and the choice of what to cite is very up-to-date.

   B. It stays focused on the topic without going into unnecessary detail (see summary style):

   The article is not long and the level of detail seems appropriate.

4. Is it neutral?

   It represents viewpoints fairly and without editorial bias, giving due weight to each:

   Except for the belief that the conjecture is true, which is properly sourced, everything here is factual; there are no significant differences of viewpoint to report.

5. Is it stable?

   It does not change significantly from day to day because of an ongoing edit war or content dispute:

   The article has continued to undergo normal editing after its May 2 nomination, but otherwise has been very stable; there are no edit wars or disputes.

6. Is it illustrated, if possible, by images?

   A. Images are tagged with their copyright status, and valid non-free use rationales are provided for non-free content:

   Images are relevant and properly licensed.

   B. Images are relevant to the topic, and have suitable captions:

   The lead animation is nice, but could use some more explanation in the caption: what do the colors and flashing arcs mean? (Also when I switch to another tab and come back, the animation has turned off, but I'm pretty sure that's a browser bug on my side rather than anything you might have control over.)

   Yeah, it's quite annoying that it does that. I'm planning to create my own animation at some point. Anyway, added a description. Ovinus (talk) 19:04, 22 May 2022 (UTC)

7. Overall:

   Pass or Fail:

   Some editing still to do, but nothing that looks like it would block eventual GA status.

I'll put this on hold to allow you time to perform these edits. Please ping me here when you are ready for another reading. —David Eppstein (talk) 07:28, 22 May 2022 (UTC)

@David Eppstein: Should be done; looking forward to your feedback. Ovinus (talk) 19:04, 22 May 2022 (UTC)

Second reading

@Ovinus: Looking better; here are a few more comments.

"she can be made stationary by subtracting her speed": Why not use the gender-free singular they again, as was already used at the start of the same section?

Done. Not sure what I was thinking.

"how well multiple real numbers can be simultaneously approximated": what is the actual implication for simultaneous approximation of this conjecture? Is it easy to explain?

unfortunately all of his work is in German, so I can't be 100% sure. In a 1971 publication he writes:

Let

$\lambda (n)=\inf _{k\in \mathbb {N} ^{n}}\max _{\alpha \in \mathbb {R} }\min _{1\leq i\leq n}\|k_{i}\alpha \|$

Is $\lambda (n)={\frac {1}{n+1}}$ or $\lambda (n)<{\frac {1}{n+1}}$?

$\|x\|$ is his (idiosyncratic?) way of the nonnegative distance to the nearest integer. That's pretty much the exact statement of our problem, restricted to integers, just in symbols. Then (I is for irrationals): This problem of the one-dimensional Diophantine approximation is equivalent to the following problem of the simultaneous Diophantine approximation:

$\kappa (n)=\inf _{\alpha \in I^{n}}\sup _{q\in \mathbb {Z} }\min _{1\leq i\leq n}\|q\alpha _{i}\|$

Is $\kappa (n)={\frac {1}{n+1}}$ or $\kappa (n)<{\frac {1}{n+1}}$?

In words I guess this means: "We conjecture that, when simultaneously approximating a set of $n$ irrational numbers by fractions of some denominator (increasing from 1), at some point you will have an error of at least $1/(n+1)$ across all approximations." Should I include this? For now I've removed the vague description of the conjecture. (I thought it was some cool generalization of Dirichlet's approximation theorem or something, but doesn't seem to be.)

That cannot be right, though. If you are approximating an irrational by rounding to the nearest multiple of 1/n, then even if you choose a bad n you will still get within 1/2n. —David Eppstein (talk) 07:21, 26 May 2022 (UTC)

I have confused myself to the moon, but yes, you're absolutely right; the minimum is taken over the error in the numerator, not the absolute errors of the approximations. If you have any suggestions on how to interpret it I'd love to know.... Ovinus (talk) 07:39, 26 May 2022 (UTC)

"A centered copy of C is placed": The switch from imperative in the previous sentence to passive here feels awkward. Why not stick with imperative?

Done

"every point with positive half-integer coordinates. A ray from the origin into the positive orthant (in other words, directed positively in every dimension)": what is the point of requiring positivity here? Is it only to avoid axis-perpendicular rays?

Yep, as far as I can tell. I did consider it, but would you prefer it say all coordinates and all rays, excluding rays perpendicular to some other axis? I feel like it requires some extra mental juggling in the 3D+ case, when the space of excluded rays is the intersection of three planes (and in general hyperplanes)

"axis-perpendicular", while having the advantage of brevity, is kind of a confusing way to explain it. "A ray that does not lie in any axis-parallel hyperplane" may be clearer, and again clearer than positivity (I'm not entirely sure what it means for a ray to be directed in a dimension). —David Eppstein (talk) 07:23, 26 May 2022 (UTC)

Perhaps. Well, it's just shorthand for "every component of a vector describing the ray has a positive component". I still think restricting to the positive orthant is easiest to understand. It's also what the source does, so it would be towing the line of OR to extend it to all of space and explicitly exclude the various planes. Also, a ray can lie in an axis-parallel hyperplane, if I'm not mistaken; take the plane $x=y$ in R3 with cubes everywhere, parallel to the z axis but containing the ray $\langle 1,1,1\rangle t$ which does indeed intersect cubes. Ovinus (talk) 07:49, 26 May 2022 (UTC)

By "axis-parallel" I meant a coordinate hyperplane; the only ones in R3 are x=0 y=0 and z=0. Also, it's not shorthand for "every component of a vector describing the ray has a positive component", but shorthand for "every component of a vector describing the ray has a nonzero component". I don't see the point of restricting to a single orthant. Placing hypercubes evenly throughout the whole space would be more uniform. In particular, regardless of how you define the rays, in "Place a centered copy of C at every point with positive half-integer coordinates" the restriction to positive coordinates is a pointless complication; it could be omitted with no loss in correctness. Similarly, I still think "A ray from the origin into the positive orthant (in other words, directed positively in every dimension)" would be both shorter and easier to understand as "A ray from the origin that does not lie in a coordinate hyperplane". —David Eppstein (talk) 16:15, 26 May 2022 (UTC)

Okay, tried to do that

"there are gaps": this term has not been explained. Maybe replace this by something like "some rays avoid all copies of C?" Or explain what a gap is.

Tried to do the latter.

"The lonely runner conjecture implies that the minimum k for which G admits a proper k-regular coloring (i.e., each node is colored differently than its adjacencies) for some step value is at most | D | + 1.": You're overcomplicating, by saying "the extremum of values with this property is x" where you could say "x has this property", again. The lonely runner conjecture implies that G admits a proper (|D|+1)-coloring.

Did this, I think

"Suppose f is further restricted to positive integers. The lonely runner conjecture implies that, if f attains at most k different values, then G has a nowhere-zero flow with values only in { 1 , 2 , … , k }." => "The lonely runner conjecture implies that, when a graph has a nowhere-zero flow with k distinct integer values, it has a nowhere-zero flow with values in {1,2, ..., k}." No need to apply restrictions to classes of functions only to restrict them again later. No need to name the flow that we are going to replace.

Done

"at which he is strictly more": again, why not they?

Done

—David Eppstein (talk) 06:29, 25 May 2022 (UTC)

@David Eppstein: Addressed stuff above; a couple questions. Ovinus (talk) 07:32, 25 May 2022 (UTC)

All issues have been addressed, so I will pass this. —David Eppstein (talk) 17:41, 26 May 2022 (UTC)

Did you know nomination

The following is an archived discussion of the DYK nomination of the article below. Please do not modify this page. Subsequent comments should be made on the appropriate discussion page (such as this nomination's talk page, the article's talk page or Wikipedia talk:Did you know), unless there is consensus to re-open the discussion at this page. No further edits should be made to this page.

The result was: promoted by SL93 (talk) 22:25, 1 June 2022 (UTC)

(

• Comment or view
• Article history

)

• ... that random runners are lonely? Source: https://doi.org/10.1016%2Fj.jcta.2012.02.002
  • Reviewed: not done (2nd nomination of mine)
  • Comment: There is barely anything "hooky" about this topic, but this is an unsolved problem in mathematics, with a partial result that, if the conditions are random, it is true (with probability one). Can't think of any alternate fun hooks.

Improved to Good Article status by Ovinus (talk). Self-nominated at 18:35, 26 May 2022 (UTC).

General: Article is new enough and long enough
New enough: Long enough:

Policy: Article is sourced, neutral, and free of copyright problems
Adequate sourcing: Neutral: Free of copyright violations, plagiarism, and close paraphrasing:

Hook: Hook has been verified by provided inline citation
Cited: Interesting:

QPQ: None required.

Overall: My only concern is that the article is technical and difficult to understand. The lede to the article does give an intelligible summary, though. I am a new reviewer. Second opinion welcome. — rsjaffe 🗣️ 21:15, 27 May 2022 (UTC)

That is a very valid concern and I'm always open to critiques. If there is anything you think can be explained more simply, please let me know; my goal is to have the introduction and most of the formulation be accessible to high schoolers, and everything south of "Implications" to be understandable to undergraduate math students. Ovinus (talk) 04:28, 28 May 2022 (UTC)