Unsolved Math: The No-Three-In-Line Problem

[@bowfuz]

i was literally just thinking about this, i mess around a ton in scrap mechanic and hate when i can't see what gates in a line are connected or not, and this is literally the problem that would solve that issue

[@SignoreGalilei]

That's an application I wouldn't have thought of, but it makes perfect sense!

[@alan5506]

Scrap mechanic?

[@2045-z6o]

​@@alan5506yes, it's a game

[@Nae_Ayy]

@@alan5506 It's a sandbox building game

[@gabe4738]

SAMEE

[@TheArtikae]

As far as lower bounds go, you can always place at least two points. That’s my contribution. Hope it helps.

[@SignoreGalilei]

Hey, that's something

[@CaesarsSalad]

Not in the case of n=1 or n=0

[@SylvainBerube]

Fields Medal incoming!

[@sebastianmestre8971]

There is a simple construction with 4 points when n>=2

[@yash1152]

7:07 this is probably the nicest or say most tangible example in my memory so far why knowing of primes is useful. it gives u anchor points about divisibility & divisibility comes up a lot in maths.

[@SignoreGalilei]

That's a good point - primes are like the divisibility building blocks of all numbers.

[@paulroberto2286]

Checkout the math behind RSA encryption for another massive use of primes :)

[@GhostyOcean]

​@@SignoreGalileifundamental theorem of arithmetic in other words!

[@SignoreGalilei]

@@GhostyOcean Yep!

[@fiartruck0125]

In 2002 or 2003 I did a summer REU (research experience for undergraduates) on a variant of this problem with triangle grids instead of squares. A few weeks in I had a nice culled-branch search program coded up in C, but other than that I wasn't making any progress so we switched to a different topic.

[@SignoreGalilei]

Cool! I hope your new topic bore fruit a little more readily.

[@ΠαναγιώτηςΓιόφτσος]

That's a great video! Pretty easy to follow, interesting and simple problem, not super handwavy, but also not extremely advanced. I'm sure you'll be featured in grants video. Great work!

[@SignoreGalilei]

Thank you! I'm glad to see I reached the goals I was aiming for, at least in your view.

[@Ganerrr]

inb4 the next step to this puzzle is some equivalence to an incomprehensible conjecture about modular forms

[@SignoreGalilei]

Lol. That's certainly not impossible.

[@pafnutiytheartist]

If I understand correctly, based on this video and Wikipedia, no N is known for which we definitely can't place 2N points. And for n ≤ 46 there are 2N solutions. I feel like the answer might be just a clean 2N but it's too tricky to prove.

[@soranuareane]

This is a good submission to SoME3 and a great video. Good job!

[@SignoreGalilei]

Thank you!

[@jxtq27]

at 0:44 the point with the checkmark is in line with points 6 and 8

[@SignoreGalilei]

Huh, I had thought I'd checked that one. Good catch.

[@jxtq27]

@@SignoreGalilei just more evidence it's a hard problem

[@jerry3790]

I may be a lowly engineering student, but it would be cool to solve one of these smaller problems one day

[@SignoreGalilei]

It would be! The Einstein (monotile) problem was in part solved by an amateur, so it does happen.

[@robertunderwood1011]

Robert Jamison Clemson University

[@myfootsitchy]

Great video. My math skills are pretty poor but I followed easily enough until at about 5:00 when the video changes from the visual representation to the algebra. I didn’t realise that the point was comparing the two slopes (from i to j and i to k). I think it would’ve been a little clearer if the algebra was done alongside the visual, with both on screen at once and in different colours. But I think I’m alone in having had this difficulty

[@SignoreGalilei]

You're probably not alone in having that difficulty. I think I decided against showing both at the same time because it would have made the screen too cluttered, but as with everything there are tradeoffs. I'm glad you enjoyed the video anyway.

[@Grizzly01]

@@SignoreGalilei Agreed with @myfootsitchy. I'd have liked to have seen a little clarification of what the contradiction was actually contradicting, as it got kind of lost along the way, and I had to do a bit of scrolling back to double check. A small gripe in an otherwise good video, though.

[@QuantumHistorian]

Very nice, but the over usage of stock photos and footage is distracted IMO. You can trust your explanations and the maths itself to keep the user engaged.

[@Tadesan]

What about their speech impediment??

[@QuantumHistorian]

@@Tadesan They dont have a noticeable one? Lots of people speak with an American accent, it's bad form to call it an impediment these days :p

[@derickd6150]

​@@TadesanYeah I'm not even sure what you're referring to

[@SignoreGalilei]

I included the stock footage because that's what I usually do in my other videos. I wanted it to feel like something I created myself rather than just a knockoff of 3b1b. That being said, I recognize that it's not everyone's favorite style.

[@QuantumHistorian]

@@SignoreGalilei Fair enough. It definitely has a fun "HalfAsInteresting" kind of vibe that I generally liked, there was just a bit too much of it. For my tastes anyway.

[@omargaber3122]

Oh my God, this video is a masterpiece, what a beauty!! What genius!!! Thank you from the heart

[@SignoreGalilei]

You're welcome! I'm really glad you enjoyed it this much.

[@BrianSpurrier]

Ok I kind of want to try my hand at this. One idea I had was to extend this to the general “No-K-in-a-line” problem. So far for the maximum number of points you can fit on an nxn grid I got F(n,k) = 0 if k=1 (no way to not have 1 in a line) 1 if k=2 (counting any diagonal angle, any two points would be a line) n^2 if n>k (you can fill the whole grid) n(n-1) if n=k (this is the only other case I can prove generally so far, basically just fill the whole grid minus one diagonal, and then swap the corners if n is even) just messing around on a chessboard I was able to find at least one solution for every case up to n=8 for f(n,k) = n(k-1) Which would fit with the 2n upper limit for k=3 I don’t really have much insight yet but my idea is that if I’m able to show that you can take a solution to f(n,k), remove n points, and have a solution to f(n,k-1), you could find a general solution by induction, but I’d need to do a lot more work to maybe get to that point

[@SignoreGalilei]

Cool stuff! It would be interesting to see if this gets a solution. I wonder what the properties are of the patterns of gaps as well.

[@Canadian_Teemo]

I know this comment is over a year old, but the line of: "n^2 if n>k (you can fill the whole grid)" had me stuck for 20 minutes trying to figure out how you could fill the whole grid if when n > k. Like a 3x3 wouldn't be able to be filled as you would easily get 1 or 2 in a line. But then I figured out it was probably meant to be k > n (/ n < k), however, I might just still be confused, so correct me if I am wrong in assuming it was a typo that n is greater than k. Edit: also the one below it says "n(n-1) if n=k" should this also be "n(k-1) if n=k" ?

[@jakehobrath7721]

This was great work, never seen this one before. Keep it up brother, you’re gonna go far

[@Tsunamicom]

What about a circle (2d space) or sphere (3d space) of r=n/2? Bigger graph size, bigger circle/sphere. It would be impossible to add points inside or outside of those shapes because then you'd always have 3 for any given angle, but otherwise you'd be at 2 points or less (tangents).

[@gaopinghu7332]

At some point, the best approximation for the circle will include 3 points for each "side"

[@SignoreGalilei]

A convex polygon works, but for big grids it winds up being fewer points than some of the other techniques.

[@gaopinghu7332]

@@SignoreGalilei for example?

[@SignoreGalilei]

​@@gaopinghu7332 Well, for n=10, the biggest convex polygon you can fit is a 17-gon but by including some extra points in the middle (like in the thumbnail) you can get 20 points with no-three-in-line. I found the 17-gon bound on the post "Big convex polygons in grids" on the blog "11011110".

[@gaopinghu7332]

@@SignoreGalilei by the way, are you italian? Parli italiano?

[@A1Ba]

@SignoreGalilei I have simple and generic solution for this problem to get 2n points. Consider grid on X-Y axis. for N+1 x N+1 grid and no K+1 points in line, 1. For 1st column, Start putting points from (0,N) till (0,N-K+1) 2. Now 2nd column, start from (1,N-1) till (1,N-1-K+1) 3. Now 3rd column, start from (2,N-2) till (2,N-2-K+1). 4. And so on. 5. If you hit at bottom of column, i.e. 0th co-ordinate of Y-axis, then start remaining points from top of the column. 5. For N-1 th column, you will have points from (N-1, K-1) till (N-1, 0). 6. Now for last column, you will have one point at (N,0) and rest points will starts from (N,N) till (N,N-K+2). I think this is the easiest generic solution.

[@YellowBunny]

I thought about doing this in a continuous space rather than a discrete one. In [0,n]² you can choose a circle which has no three points lying on a line. That circle has τ/2*n "many" points which is surprisingly larger than 2*n. I was hoping that this would have some similarity to the limit as n goes to infinity in the discrete case. But that doesn't seem to be the case and arranging the points in a circular shape doesn't seem to be all that good for n>4.

[@SignoreGalilei]

I found a link somewhere saying that if you use convex polygons for n=10, for instance, you can only place 17 points instead of the 20 you can get if you add some in the middle.

[@fabiansalinas946]

In R^2, one can show (using axiom of choice; e.g. transfinite induction) that there exists a set S that intersects every line in the plane in exactly two points. Similarly, there exists a subset of R^2 that intersects every circle exactly 3 times. I think that a similar claim can be made for bounded subsets of R^2 (may need to impose nonempty interior to not fall into the discrete case). There are still unsolved problems in the continuous case, namely what kind of properties such a set has. In any case, this video was pretty good, and I had never considered the discrete case. Definitely enjoyed watching.

[@SignoreGalilei]

@@fabiansalinas946 That's cool! Some Banach-Tarski type stuff going on I suppose. I will have to check out that proof somewhere.

[@strafeae4618]

Great video! I never knew about that rule for dividing in modular arithmetic

[@SignoreGalilei]

Glad I could teach you something then! And thanks!

[@admiralbananas]

I honestly can't believe how complicated this got! It seems like such an innocent problem...one that would have a really convenient solution or trick.

[@SignoreGalilei]

Yeah! This is one of main reasons that I decided to cover this particular problem.

[@YLLPal]

Before watching, my initial guess is: Pi*D, where D is the side length of the grid. The image is of course inspiration, but I think is make logical sense. Taking the case of a continuous "grid", the best way to make sure a line drawn in the box meets at most 2 points is to have a continuous convex shape. This way there aren't any inflection points, which cause 3 point intersections or straight lines, which are ruled out by default. It makes sense to me that the grid density would affect the "resolution" of the circle, which is why a continuous has infinite points, and a circle on a 2x2 grid has 4 points. So Pi*D, where D is the grid size.

[@SignoreGalilei]

Convex shapes do work as solutions, but for some large grids they do worse than other types of solutions. Good prediction about pi showing up though!

[@josephyoung6749]

there's something very orderly and symmetrical about the results of the dots. I wonder if this could be a jumping off point to finding the solutions.

[@SignoreGalilei]

One website I saw (Flammenkamp's) orders the solutions by their symmetries, so it probably does make a difference there.

[@Kyle-nm1kh]

It's a geometric problem at its base

[@0u0ak]

An interesting check would be, for any given solved n x n grid, look at how many dots must be removed from any two edges to shrink it to a n-1 by n-1 grid. This may suggest a general solution. This problem may be easier to solve it in reverse - how many points must you remove from a grid so that no three points are in a line. Solve for odd number n, solve for even number n and come up with a generalisation and odd/even modulus (ripple) should have a repeated effect on the outcome. The answer will likely be iterative permutations that add up in a similar fashion to triangle numbers, but including quirks of 2D. Then tackle the harder cases of n x m, n x n x n (a cube) and m x n x o. Comparing with 1 and 3 in a row might help. Algorithm-wise, you could either attempt it via (1) a deterministic branching walk according to rulesets, or (2) by using a random filter (flood the grid, pick random x,y and remove a point if it has two neighbours in a north, south, east or west direction, repeat n x n times (at maximum), and save the first 10 or 100 solutions for each n for further analysis, but only for the highest (and lowest?) number of dots. There are many ways to speed this up (e.g. iterate all x,y and if turning the point on won't break the three-in-a-row rule, turn the point on according to some random factor. e.g. working with coordinate lists or multi-linked arrays/lists).

[@SignoreGalilei]

That would be a cool check to run - if you end up coding it, let me know! I'm not super familiar with making efficient algorithms, but I'd love to see what people come up with. There was another commenter wondering about the reverse problem as well.

[@apollo261]

Amazing video! Never heard of it before...

[@SignoreGalilei]

Thanks!

[@coopergates9680]

Nice walkthrough. It's intriguing that the conjecture involving pi over the square root of 3 is substantially broken for n = 52 with that solution of 104 points. Maybe the max ratio drops off very slowly as n grows?

[@BrianSpurrier]

The only issue I have with the educated guess method is that it doesn’t matter if the chance that you could get 2n points with no three in line by chance is low. Just that there is one. The odds of rolling all sixes as you add more dice goes to zero as the number of dice increases, but the answer to the question “is there an arrangement of n dice with n sixes” is still yes. Likewise, as long as there is at least one way for there to be n points with no 3 in a line, it doesn’t matter if there is practically a zero chance of getting it randomly, it’s still there

[@tetronym4549]

The way I understood it is that you don’t know what the actual chances are. They’re measuring their uncertainty ABOUT uncertainty. Imagine you asked the same question but instead of n 6-sided die, you had n random DnD dice. For all you know you have a d4 in there and the probability of n 6s is zero. So you factor in the probability of all n of your die being d6s first, then the probability of their faces all being 6.

[@SignoreGalilei]

It's true that you only need one way, but it's not just that the chances of getting it on each specific try go to zero, it's that the chances of getting it on each try **times the total number of tries you get** goes to zero. In your dice example, that product stays at 1 no matter how many dice you add.

[@matteopesce7405]

Instant subscription just for the name of the channel

[@SignoreGalilei]

Thanks!

[@elunedssong8909]

Love the video, though i'm not convinced the statistical approach isn't just a book closed type of thing, i'm sure there isn't much better you can do, if you already know what the upper and lower bounds should tend towards. Seems like they killed it!

[@SignoreGalilei]

It's a great result. I'd say the open question is whether there's a systematic way that you can do better than the statistical expectation, at least for certain types of numbers (e.g. primes or something).

[@elunedssong8909]

@@SignoreGalilei Gotcha, thanks!

[@hellNo116]

i love how we call something educated guess, and the educated guess has its own proof. i know it makes sense, but i can't stop feeling it is a little funny that in math the vibe check is a "simpler" "easier" proof.

[@Joshkl2013]

I feel like theres some way of conceptualizing this using similar principals to valence electrons where you have general inner patterns which appear for larger N (e.g. an inner pattern for n=8 might appear on n=16). But I'm an engineer, not a math guy =P

[@SignoreGalilei]

I know Flammenkamp looked for this kind of pattern. I don't think he's found any yet, but you're on a good track here.

[@morosov4595]

As a programmer my initial idea was to create a program that checks every possible combination and hope that I will have enough computing power.

[@SignoreGalilei]

That would help, but the number of combinations grows as n^2 choose 2n so you may run out of computing power pretty quickly.

[@morosov4595]

@@SignoreGalilei Yea, but by then I might find a patern, and if I suspect a number of points I only need to brute force 2 amounts of points - One that's possible x and x+1 that's impossible.

[@SignoreGalilei]

@@morosov4595 Certainly even finding one size grid where no 2n configuration is possible would be a step forward.

[@morosov4595]

@@SignoreGalilei Well then, I guess it's time to boot up cuda and get to work.

[@clarencejohncabahug5466]

I asked that kind of question on Quora for fun four years ago! I didn't know that the general problem was unsolved, lol. I just solved it upt to n=6.

[@HoSza1]

Has anyone tried to tackle the generalised version for higher dimensions? This one would be a special case, d=2, s=3

[@stargazer7644]

I'm sure that would be much easier. lol

[@SignoreGalilei]

I think people have tried it to some extent. Not sure how far they've gotten.

[@mattc3581]

Should try using a grid on a torus, solving the torus case is always easier than the 2d surface in maths :)

[@fibbooo1123]

Awesome video!

[@SignoreGalilei]

Thanks!

[@iwersonsch5131]

so 1.8138n + o(n), with o(n) probably still being quite significant at n=1000 I imagine

[@SignoreGalilei]

Yeah, I believe the conjecture specifies that the part other than 1.8318n is sublinear, but it still probably makes a difference at n=1000

[@aether222]

Ok, I haven't watched this yet but, it seems pretty clear that the design at the start should be the maximum. At least it seems to meet the requirements to me and there are two dots on every horizontal and vertical line. And while there might be some diagonal where that isn't the case it would be easy to test for each unique position. So I'll try watching it but at first blush it seems obvious the answer in the grid shown is (at most) 20.

[@aether222]

just confirmed, no to are in a line, at least nit if we assume we are only interested in a perfect line or where the circles are smaller where shown.

[@SignoreGalilei]

Yep, 20 is the best solution for n=10. The question is how far that pattern goes.

[@Lykos93]

don't mind me being a D&D DM who uses math problems like this this one to create puzzles for my campaigns.

[@giulio4217]

5:50 It's (15 mod 5)/3=0 not (15 mod 5)/5=0. It doesn't change anything but I wanted to tell you. Also great video.

[@SignoreGalilei]

Thanks for catching that. I'll add it to the corrections section.

[@rtheben]

Great video! Many thanks

[@SignoreGalilei]

You're welcome!

[@TheOneMaddin]

"How can this still be open?". For most questions of this kind I don't see how they would not be open. First, what do you expect. There are infinitely many grid sizes so you cannot just try all ways in all grids. I would be much more intrigued if there would be a finite problem that is still open (like the existence of the missing Moore graph). So what you probably want is a formula in, say, n. But there is almost never a formula for anything, so I am not surprised. Keep in mind, there is not even a formula for the product of the first n integers... we just make up the notation n!. So you are probably looking for an asymptotic formula. But now we enter regimes that many people are not too familiar with and that many non-mathematicians would be reluctant to count as "solving the problem". And then I also always though these combinatorial problems are so generic, that once solved I can just tweak it minimally and get a completely new problem that is now again "surprisingly" open. For example, consider 3D grids, or no 4 points on a line, or no 4 points on a circle. Finally, for this particular problem in the video I don't see why it should be easy to solve. No three on a line in a grid is connected to number theory which is intrinsically hard. Having said that... I will watch the video now and it will surely be interesting :D

[@sk8erJG95]

"There are infinitely many grid sizes so you cannot just try all ways in all grids" What? That has never been an issue in any area of mathematics. No one who has done even a bit of math expects brute-forcing to work. It's pretty much the first thing you'd learn in a proofs course, e.g. when learning induction or any other proof method.

[@TheOneMaddin]

@@sk8erJG95 Have you read the rest of my answer. I am building up an argument, and that is merely the first piece. Admittedly, it's a very weak one (and I maybe should have dropped it).

[@yrodro]

3 points in a row is too difficult. perhaps start thinking about the same problem with 2 points?

[@SignoreGalilei]

How about 1 point?

[@yrodro]

@@SignoreGalilei oh! I think that was solved before Euler

[@ChrisContin]

Nice video explanation! Must’ve taken a lot of work.

[@SignoreGalilei]

Thanks! It was more involved than most of my videos because of all the animations, but I hope it was worth it.

[@egilsandnes9637]

I guess this variation is much harder to solve*, but it's what I thought the problem would be before you explained it properly: Fill the grid with as many points you can without any three points on the same line be placed such that the middle point isn't exactly in half way between the two other points. (There's a sequence in OEIS with this property, so that no 3 points will make up a "symetric" line in a 2d plot) *(Though you never know. Sometimes problems that seem harder are easier to solve than those that seem easier.)

[@jamesdavis3851]

If it's convenient - what is that sequence?

[@egilsandnes9637]

@@jamesdavis3851 I've tried to find it, but haven't succeded yet. I'm like 98% sure it was featured on Numberphile with Sloan himself, and I think it had quite and interresting graph. I'll let you know if I find it.

[@SignoreGalilei]

That sounds like a cool variation. And yeah, sometimes more restrictions actually make a problem easier.

[@jonathanfontaine2325]

@@jamesdavis3851 It starts 1, 4, 6, 9, 16, 17. Plugging this into OEIS immediately gives you A300131. It only lists values up to n=12.

[@ri-gor]

Just a couple seconds in and I already feel a little silly: I misunderstood the problem and thought "couldn't you just make a circle to have an infinite number of points? That would make it so you have at most two collinear points for any given line". I initially missed the statement that they had to be on the intersections of the coordinates lol.

[@SignoreGalilei]

Haha yeah that is an important bit of the statement

[@gamersedge891]

I mean, if you had an infinitely dense grid, a circle would be a valid solution (I think. Feel free to correct me if I'm wrong)

[@tediustimmy]

I just found this. I took two hours to code up a brute force solution and it took over an hour for a 9x9. The 8x8 takes less than a minute. There's too much freedom for brute force. Though, looking at the problem. Is every 2N solution always decomposable into two Latin squares?

[@JNasim]

What software do you use to make your presentations. Any recommendations on how to learn it

[@SignoreGalilei]

Manim Community Edition for the geometry animations, OpenShot for the video production. Both have good documentation and Manim has a discord server. Manim is easier if you've already learned Python programming, though.

[@TymexComputing]

Very rational problem, simple definitions and explanations and the intended puns about Galileo :). Is this connected to the Riemann hypothesis?

[@SignoreGalilei]

I'm not sure if it's connected to the Riemann hypothesis. It seems like it could be given the way slopes work.

[@emmettnelson7260]

I feel like this question would be much easier to solve on a nxn toroidal grid, just like how considering the n-queens problem on a toroidal grid takes its difficulty from almost impossible to solvable in about 1-2 hours.

[@BlueRaja]

Great video! A small suggestion though - the stock clips are tacky. The next video would be better without them.

[@MikeRosoftJH]

Is there a known size for which it's not possible to place 2*n pieces?

[@SignoreGalilei]

Nope! The number of 2n configurations is roughly n^(4n) so it's computationally quite hard to make an exhaustive search.

[@blacklight683]

Ai:am about to run 3billon 900millon simulation to find this out in 3months max

[@SignoreGalilei]

Good luck! Let us know if you find something cool.

[@oncedidactic]

1:48 that’s Professor Mathrülz, not General Mathrülz, his sister. They are oft mistaken for the way they both lean back casually while explaining with a stick.

[@SignoreGalilei]

Gotta appreciate women advancing in the military. Nothing but respect.

[@andrea-mj9ce]

Is it possible to apply the stimulated annealing technique to get a lower bound empirically?

[@SignoreGalilei]

That seems like it could be promising. Another commenter mentioned dynamic programming as a possibility as well.

[@bengoodwin2141]

For a moment I thought "hey, of course you can always fit p points on a p^2 grid" but then I remembered diagonals. I wonder how the solutions change if diagonals are ignored?

[@SignoreGalilei]

I believe you can always get 2n if you ignore diagonals: place n points along one main diagonal, n-1 points on the line right below it, and the last point in the opposite corner.

[@bengoodwin2141]

@@SignoreGalilei I thought so. I wonder if more is possible with those rules? Probably not

[@SignoreGalilei]

@@bengoodwin2141 Nah, I think the pigeonhole principle argument on the rows still works.

[@NikolajKuntner]

nice animation

[@SignoreGalilei]

Thanks!

[@MrHerhor67]

How is it that modulo is distributive? For example, 1 mod3 - 2 mod3 != (1-2) mod3 Does it only work in that particular case where i and j are nonnegative and also j > i?

[@SignoreGalilei]

((1 mod 3) - (2 mod 3)) mod 3 = (1-2) mod 3 - as I recall, this more complicated relationship always works. Then since i, j, and k are whole numbers less than p, we can make the appropriate cancellations.

[@MrHerhor67]

Right, I remember something like that, though can't really prove that in head, but I think it worked at least for positives. Anyway, that's a pretty good video, even though it took me two attempts. Maybe that was because of the voice, I had a bit of trouble understanding sometimes. One thing which would also be nice to add, is a combined animation at the end to remind how the U&L bounds changed throughout the vid.

[@sk8erJG95]

"Mod" isn't exactly an operator in that case, it's more like a different environment we're working inside where everything is constantly being taken mod 3. Which is essentially saying that (1mod3 - 2mod3)mod3 = (1-2 mod3) At a higher level, you can prove that the "mod p" map is a ring homomorphism, which means most algebraic properties of Z will be preserved when looking at Zmodp. The way you wrote the equation has Z on the lefthandside but Zmodp on the righthandside, which is your issue.

[@SignoreGalilei]

Yeah, I kinda handwaved the difference between the operator of taking a remainder and the idea of modular arithmetic. It feels like a topic for another video, not this one.

[@lool8421]

if it was a plane instead of a grid, the answer would obviously be infinite because there are infinite transcendental numbers

[@TheOneMaddin]

A pigeon hole is not a dirt hole with pigeons xD.

[@tomaszmaciocha4991]

Ladies and gentlemen, I am extremely pleased to say, that solution of this problem for a given n exists.

[@SignoreGalilei]

Congrats haha

[@yoursleepparalysisdemon1828]

dont you just have them go diagonally from one side to another? edit: ohhh also in diagonals

[@SignoreGalilei]

Yeah, the diagonals make it harder.

[@drdca8263]

So does the conjecture then say that there is a largest n such that 2n is achieved? I imagine the conjecture is that the limit of the ratio (number of points)/n converges to k = pi/sqrt(3) ? Hm... This brings to mind another question: suppose we look at (max number of points for n) - kn, and look at how large a range of values that can be in, and like, rescale it to keep the range independent of n, and then we take a “random large n”, would the distribution over this rescaled difference, converge to some nice distribution? (Where by “random large n” I mean like, the usual way of pretending there is a uniform distribution over the natural numbers, even though there isn’t.) Could the same approximation used to justify the conjecture be used to come up with a heuristic estimate of a distribution for what the max number of points that fit in an n by n grid is? Like, if we pretend that for any 3 points in an n by n grid, the probability that they are co-linear is independent of the chance for any other 3 points, So, for the n by n grid, there are (n^2 choose 3) independent random variables, each with a probability (the function of n described in the video) of being “yes, these 3 are co-linear”, then, hm, there is a random variable associated with this setup which is “what is the size of the largest subset of the n^2 points such that no 3 among that subset has their associated random value be “yes, these 3 are co-linear”. This seems like a distribution that would be difficult to characterize... Maybe it could work to say, after those random values for co-linearity have been picked, independently, randomly select a subset of size j of the n^2 points, and then estimate the probability that all subsets of size 3 of that subset have an answer of “not co-linear”..? And I guess then the task is evaluating, what is the probability that the values of “which triplets are co-linear” are such that [given these values of which triplets “are co-linear”, the probability that the randomly selected subset of size j, contains no “co-linear” triplet] ? Does that make things any better? Hmm.. Well, P(A or B) \le P(A) + P(B) so... if adding points to the subset one by one, the chance that at least one of them is “co-linear” with two that were previously added, is at most the sum of the probabilities of each of them individually being that way, and... hm, this line of thinking seems to us the joint distribution though, not the “probability under one distribution that the probability of another thing under a distribution depending on the value from the first one, being non-zero”... Well, I guess P(X is s.t. P(f(X,Y) | X) > 0) is, greater than or equal to P(f(X,Y)) (where f(X,Y) is a predicate) so it should give a bound in one direction.. So, continuing... the chance of a newly added point being “co-linear” with a previously added two points (where, again, all the “co-linearities” are independent) should be bounded above by (the number of pairs amongst previously added points) * (the chance of a triplet being “co-linear”) and so, \sum_{i=3}^j ((i-1) choose 2) * (probability for a given triplet being co-linear) gives an upper bound for probability of a randomly selected j points, containing a “co-linear” triplet. (i-1)(i-2)/2 summed up to i=j .. well, it will be a cubic in j, for j=1,2,3,4,5,6 it is 0,0,1,4,10,20 should have (j-1)(j-2) as a divisor, so what ratio remaining? 2,6/4,12/10, 20/20 wait what? That’s not linear.. (1/2),(2/3),(5/6),1 ... I’ve made a mistake somewhere... Anyway, I should stop working on this and get to work..

[@SignoreGalilei]

I'm not 100% sure, but I think your heuristic might work better the farther k is from 2, since as k approaches 2 you have nonlinearities as the number of available spaces drops faster than expected. If you end up working on it more, let me know - I'd absolutely love it if someone made progress on the problem based on comments from this video!

[@jeremy.N]

Very interesting conjecture, do the current best known results confirm that? Like is there anyone who has tried to find optimal choices for n=1000 or so and maybe they managed to fit in 1800 points?

[@SignoreGalilei]

I don't know if anyone has tried that specifically - it would be cool to do.

[@tinfoilhomer909]

Of course we can always reach the upper bound

[@caiodavi9829]

when we got the 1.5 lowerbound i thought we were heading towards e

[@TheGoodMorty]

How about the question of n×n grid with no m points in a line (rather than just no 3 points)

[@SignoreGalilei]

That's a good extension of the problem - I think there have been some investigations into that but I'm not sure what the results were.

[@emilyyyylime-]

11:15 in the exponent, is that supposed to be -3nk³ or -27nk³ (with the cube outside the parentheses)? Either way the form written in the video is rather unnatural which made me have doubts

[@SignoreGalilei]

Just the k is supposed to be cubed.

[@SkorjOlafsen]

7:18 That 1974 font. 🤣

[@SignoreGalilei]

Thanks haha

[@GAAgoodatauto]

0:12 U-COHL'S is probably solved and in the future, also. it will be solved.

[@GAAgoodatauto]

The "it" is the problem that is in the title now, ngl.

[@Speedster___]

How does this chnage if grid is size n by n+c

[@SignoreGalilei]

Your upper bound is still going to be twice the size of the shorter axis by the pigeonhole principle, but it might be easier to achieve that bound.

[@GordonHugenay]

So there is no explicit example where the number is smaller than 2n?

[@SignoreGalilei]

Not that I could find, no.

[@pulsefel9210]

if its been solved that there will always be for a prime, you know its always possible since you can never get an end to primes.

[@SignoreGalilei]

Yep, that would mean there would be infinitely many solutions. We haven't quite gotten all the way to 2n even for the primes yet, though.

[@cxpKSip]

A simple tiling shows that the maximum number for a grid of size m×n is 4mn÷9. Ah. Any straight line. We can solve this algorithmically...

[@SignoreGalilei]

Right, the diagonals make this a lot harder

[@EpicBoss-]

I'm still confused about 1 thing. Around 8:30 It was shown that there are at least 1.5n points for an n that is twice a prime number, how is that true for all n

[@SignoreGalilei]

It's not going to be exactly 1.5n for every n, but it will be fairly close as long as there's a prime number not too far below n/2. The prime number theorem tells you about how far off you'll be - it becomes a smaller and smaller proportion of n as n gets bigger.

[@ishandutta4833]

isnt there a typing error at 5: 51 in the bottom line it should be 15 mod 15 / 3(not 5)

[@SignoreGalilei]

Yep, I've put that in the corrections I believe.

[@vaap]

at 6:10, why is p prime? i thought p was the size of the grid

[@vaap]

oh i watched a little more and i guess p is a chosen prime between n and 2n, im not sure if u had mentioned that before introducing p but that makes sense

[@SignoreGalilei]

I'm pretty sure I do mention it, but it might be pretty brief.

[@niall4588]

I offer an alternative problem. What is the least number of points that can be placed on an n-by-n grid, no three in a line, such that the addition of one more point must contain three in a line? Enjoy

[@SignoreGalilei]

Martin Gardner spent some time analyzing this one - it's a noticably smaller amount.

[@RoderickEtheria]

Surely infinite, right? If you throw in all transcendental numbers? Then, again, if all transcendental numbers could be placed on such a grid, there would be countably many of them, and transcendentals are uncountably many.

[@SignoreGalilei]

The problem here is specifically if you restrict it to the integer grid points. I think even if you only expand that to rational numbers you can fit infinitely many.

[@RoderickEtheria]

@@SignoreGalilei Rational numbers can be used. There are as many rational numbers as integers. Irrational numbers would have an issue.

[@SignoreGalilei]

@@RoderickEtheria I may be misunderstanding your point. There are indeed as many rational numbers as integers, but integers are all a certain distance apart where as rationals can get as close together as you'd like. Would this not mean you could place a (countably) infinite number of points on the grid if the points' x and y coordinates are allowed to be any rational number?

[@RoderickEtheria]

@SignoreGalilei Precisely. Rational numbers are countable infinite, so you can place them all on an infinite grid. You can give each of the infinite rational numbers an integer value, and there would be no difference in the grid besides the distance between points. It wouldn't change the problem. Throwing in any irrational numbers prevents the grid. There is both countably infinite many integers and countably infinite many rational numbers. Their infinites are the same size, and so a grid could be made of either and solve the same problem. There is no difference in the size of the grid if you have a space between .0001 and .0002 or 1 and 2. Or any other degree you label the rational vs. integers. Irrational numbers couldn't be labeled on such a grid, nor transcendental numbers. You already posited a grid with countably infinite points the moment you specified all integers. The issue arises between countable infinite to uncountable infinite, not between integer and rational.

[@adarshk7484]

i had subtitles on at the start information overload

[@SignoreGalilei]

Sorry about that haha

[@kannix386]

why did you say that we haven't made progress on the collatz conjecture? didn't terence tao prove something that's like 99% there?

[@SignoreGalilei]

I think it's not 99%, but it is definitely progress. I was being a bit dramatic, I suppose.

[@TymexComputing]

Fine... 7:10 the halved theorem is not true that's why we all remember it by n by 2n :). Lower boundary. There is no prime in between 2/2 and 2 for a simple 2>1

[@TymexComputing]

Did I win something? :) is this the 3🖥1🏀 voice?

[@SignoreGalilei]

The original source I grabbed the n/2 from used a ≤ rather than a

[@TheWolfboy180]

3:12 how? how did you insert a flag meme

[@SignoreGalilei]

I remembered that one from EU4, actually. I've had a few "so" gags in my videos before - sewing, sulfur monoxide, etc.

[@SaltPep]

Cool

[@SignoreGalilei]

Thanks!

[@SuperMaDBrothers]

dynamic programming

[@SignoreGalilei]

That would probably help with individual grid sizes, but not if you want to know a general formula for all grid sizes at once.

[@SuperMaDBrothers]

yeah lol cool video!@@SignoreGalilei

[@SuperMaDBrothers]

ill give you a hint in solving the problem: write it recursively. general formula is not too hard to derive from there.

[@SignoreGalilei]

@@SuperMaDBrothers Thanks!

[@tracyh5751]

Doesn't the statistical argument provide a new upper bound? A subset of a finite set with zero probability must be empty.

[@SignoreGalilei]

The issue is that the probability is not quite zero. It's small enough that the expected value is much less than one, but still positive.

[@iluxa-4000]

Well, I can surely say that you can put 2 points

[@SignoreGalilei]

Hey, you gotta start somewhere

[@omchavan5664]

Where can I get more data about this You know I am gonna prove this

[@SignoreGalilei]

You can start with the linked papers and Flammenkamp's webpage. Good luck!

[@Morrivar]

Explanations in this assume the viewer knows things most people don't. For instance, you don't explain why finding a contradiction isn't just proof your math is wrong.

[@SignoreGalilei]

That is true. I've gone over the ideas of proof by contradiction in other videos, so I didn't feel the need to do it again in this one. There's always a balance to be struck between getting straight to the point and making stuff more accessible.

[@HoSza1]

Where should one start digging? (other than googling the question😂)

[@SignoreGalilei]

The sources in the description are where I got my info - they might help.

[@HoSza1]

@@SignoreGalilei Thank you!

[@SignoreGalilei]

@@HoSza1 You're welcome!

[@kikojukic9156]

5:50 you forgot to put 4 in (4+1)mod15. it is not 4 + 1mod15

[@kikojukic9156]

Very grate video tho

[@SignoreGalilei]

Yeah, parentheses probably would make that one clearer, though the value of both expressions is the same.

[@Henrix1998]

10:35 AAAAHH MY EYES

[@SignoreGalilei]

The comic sans or the light mode?

[@Henrix1998]

@@SignoreGalilei sudden light mode. Great video otherwise but I wish it was longer. Maybe that's not really possible when it is unsolved problem.

[@SignoreGalilei]

@@Henrix1998 That's fair. It's already a bit longer than most of my videos.

[@beaclaster]

this sounds somewhat similar to sudoku

[@SignoreGalilei]

It does, now that you mention it. I wonder if any techniques would overlap between the two.

[@machiavelli976]

Great video for a useless problem ! BHHUHUHUHAHAHAA !!!

[@SignoreGalilei]

You laugh, but to pure mathematicians that's an incredible compliment.

[@nathandean5869]

not anymore. i just solved it

[@SignoreGalilei]

congrats

[@sebastianrossetti6167]

The volume is way too low man

[@SignoreGalilei]

If I raise the volume on my editing software it makes it distorted. You may just have to raise the volume on KZbin.

[@OrenLikes]

way too many ads

[@EdbertWeisly]

The thanks for watching gives Vsauce vibes

[@SignoreGalilei]

A few people have mentioned that one, haha

[@gdplayer19]

Might need to fix the subtitles, buddy.

[@SignoreGalilei]

What's broken about them?

[@gdplayer19]

@@SignoreGalilei They weren't segmented and all appeared as one paragraph that blocked the whole screen.

[@illustrious420]

0:12, isn't collatz conjecture solved last year already?

[@jamesdavis3851]

Supposedly, but Tao said there wasn't enough space in the stack exchange buffer to upload the proof

[@SignoreGalilei]

I don't think there's a full proof. Terry Tao was able to prove some information about its long term behavior, but not the original full conjecture.

​@@SignoreGalileiNo sadly. My own approach has even got further.

No, I haven't yet, bu I'm close. Neither have Tao, I believe.

[@deleted-something]

Oh wow

[@SignoreGalilei]

Thanks!

[@deleted-something]

@@SignoreGalilei does this problem become unsovable with any value N > 3? And is there an analogy in three dimensions?

[@SignoreGalilei]

@@deleted-something There definitely is an analogy in three dimensions - and higher too. For lines with more than three points, the pigeonhole principle bound still works, but I'm not sure what else is known.

[@XiaZ]

Unsolved? Let me introduce you to Brute force and Computer.

[@SignoreGalilei]

That's only taken us up to n=52 so far, but I'd be happy to see what happens beyond that.

[@XiaZ]

@@SignoreGalilei Try a better computer next time.

[@danielyuan9862]

​@@XiaZbrute force rarely works when the problem is infinite

[@XiaZ]

@@danielyuan9862 When you want N = Infinity, I wonder why you don't give Infinity time complexity too. If you want to run on low time/memory complexity then next time specify that in the problem.

[@SignoreGalilei]

I think the issue is the definition of "solved". For any specific large n, brute force will eventually get you the answer, but if you want to know the answer for every possible large n at the same time, brute force will literally take infinite computations.