Thread: Finding a point in an infinite space

1. Finding a point in an infinite space

There is a plane where the X-axis goes from -∞ to ∞ and where the Y-axis goes from -∞ to ∞. You know that somewhere on the plane is a point whose X and Y values are both whole numbers. Your goal is to find this point, but you can only ask yes/no questions about the point; there's no limit on how many such questions you can ask, nor on the complexity of the questions, save that they must be answerable with a binary "yes" or "no" answer. Can you find the point, and if so what is your method?

2. Re: Finding a point in an infinite space

Pretty easy; "is the y coordinate greater than 0?" Repeat for x. Now you know which quadrant it's in. Repeat basically the same questions, increase the number you ask about by.. Oh a billion or so until you get a broad zone to narrow into. There's probably a more efficient algorithm, but it's not hard to do.

3. Re: Finding a point in an infinite space

Originally Posted by tyckspoon
Pretty easy; "is the y coordinate greater than 0?" Repeat for x. Now you know which quadrant it's in. Repeat basically the same questions, increase the number you ask about by.. Oh a billion or so until you get a broad zone to narrow into. There's probably a more efficient algorithm, but it's not hard to do.

And that's true whether the large number you increased by is one billion, one septillion, one google, one googleplexion, or any other non-infinite number; it doesn't matter how big the number you're increasing by is, infinite is infinitely bigger. If each of an infinite series of questions can only eliminate an infinitesimally small sliver of the remaining possibilities, can the point always be found? Even if the method is refined in such a way that you exactly eliminate half of all remaining possibilities, does dividing infinite by 2 produce something besides infinite, if done enough times?

4. Re: Finding a point in an infinite space

Do you have a countably infinite or uncountably infinite number of questions? If countably infinite, then sort the points into a line (for instance, by 2pi * distance first and then by angle) and ask one by one. That will take an infinite number of questions, but it's no less efficient than any other method that requires an infinite number of questions.

5. Re: Finding a point in an infinite space

A constructive method for locating the point is to do the following for each coordinate:
1) ask "is the number zero" If it isn't continue
2) ask "is the number positive?". Store the sign somewhere, and continue
3) set n = 1
4) ask "is the nth in the number's binary representation one?"
5) ask "is there a n+1st term in the number's binary expansion?" If yes, set n = n + 1, return to step 3. If not, you are done.

Repeat steps 3 and 4 until there isn't a next term. When you finish, you will have the binary representation of the number, hence the number. This method is guaranteed to terminate in no more than 2 + 2*d steps, where d is the number of digits in the binary representation.

(Finding the point is, mathematically speaking, trivial. The cardinality of whole number pairs in R2 is countably infinite. Since you get unlimited questions, simply diagonalizing your way through all (x, y) pairs of whole numbers will get you the solution. However that answer's no fun at all.)

6. Re: Finding a point in an infinite space

If you can only ask a finite number of questions, no the point can not be found in general. Otherwise, well...

My method would be to ask about the factors of coordinates. Start with "is the x factor divisible by 2" which eliminates half the points. Then ask if it is divisible by 3, if the answer is no, and 3 * 2 if the answer is yes. Repeat for all primes. Because each number is uniquely factor able into primes I think you would get the answer. I suspect it would take ω steps though.

Edit: I like warty goblins method too.

—Caerulea

7. Re: Finding a point in an infinite space

Your search space is infinite, but the value you are looking for is not, which means we can ask useful questions about it regardless of the infinities. How about something like "Assuming Times New Roman in a 12-point print, can the (x or y) coordinate be printed in its entirety on a single line of a standard 8.5 x 11 page of printer paper?" If not, ask again, but use scientific notation. If still no, go to whatever your favorite method of rotating excessively large numbers is. That will eventually get you a (admittedly very, very broad) placement of at least the magnitude of the number you are looking for, and once have that you can refine further...

Or if want to brute force the whole process "Is the (nth) digit (0-9)? Is there an (n+1th) digit? Is the (n+1th) digit (0-9)?" Iterate until you are told there aren't any more digits. Super tedious, sure, but also the sort of thing that's really straightforward to feed into a computer and just come back later to check the progress.

8. Re: Finding a point in an infinite space

Hmm...the point about countable infinities vs uncountable is I think the stumbling block that was making it difficult for me to wrap my head around, but different degrees of infinite makes it a bit easier. Would an uncountably infinite number of questions be insufficient to determine the point if it was "numbers" instead of "whole numbers", since that opens up fractions and irrationals and makes the problem also an uncountable infinite, or is the uncountable infinite of the problem still not so large that the uncountable infinite of the solution couldn't solve?

9. Re: Finding a point in an infinite space

Originally Posted by AvatarVecna
Hmm...the point about countable infinities vs uncountable is I think the stumbling block that was making it difficult for me to wrap my head around, but different degrees of infinite makes it a bit easier. Would an uncountably infinite number of questions be insufficient to determine the point if it was "numbers" instead of "whole numbers", since that opens up fractions and irrationals and makes the problem also an uncountable infinite, or is the uncountable infinite of the problem still not so large that the uncountable infinite of the solution couldn't solve?
A countably infinite number of questions can find the point (and, relatedly, rationals (fractions) are countably infinite).

An uncountably infinite number of questions can determine the point if it's 'numbers', though 'uncountably infinite discrete objects' (e.g. questions) seems a bit of a suspect construction in its own right and probably requires a bit more care than I'm giving it. To be more careful, I think one would want to define a dense manifold of questions and then ask whether there's some aggregation function that collects the answers which identify the point uniquely from the manifold - e.g. the questions are given by Q(x,y) = delta( (x,y) - (point_x, point_y) ) and the location of the point is the integral dx dy (x,y) * Q(x,y).

10. Re: Finding a point in an infinite space

I think Tyckspoon's method gets a bit better if you start using powers. Don't divide the grid into blocks one billion by one billion, but rather 9 zeroes by 9 zeroes. The number, assuming it was picked by a human, is likely to be relatively small, so it makes sense to have a finer search grid in the low numbers, and expand it from there.

This is still not fast enough to find something like Graham's number (or rather the coordinate Graham's number by -(Grahams number/pi)^146-77854) on a human asking questions timescale, but at that point I think even the most elegant methods will struggle.

11. Re: Finding a point in an infinite space

Originally Posted by Lvl 2 Expert
I think Tyckspoon's method gets a bit better if you start using powers. Don't divide the grid into blocks one billion by one billion, but rather 9 zeroes by 9 zeroes. The number, assuming it was picked by a human, is likely to be relatively small, so it makes sense to have a finer search grid in the low numbers, and expand it from there.

This is still not fast enough to find something like Graham's number (or rather the coordinate Graham's number by -(Grahams number/pi)^146-77854) on a human asking questions timescale, but at that point I think even the most elegant methods will struggle.
Instead, project the infinite plane on a finite one using any bound analytic function like for example ArcTan. For whole numbers this should be as fast as warty goblin's algorithm, since it also uses splitting the plane in halves regarding the specific digits in binary representation.

By using more general questions and slicing the scaled down infinite plane in a natural geometric way, one can approximate any sought number much faster and obtain any desired precision in finite time even if we consider any real number pairs. Cosidering how real numbers are constructed as a limit of rational sequences, we will also obtain exact result in countable infinite questions as well.

12. Re: Finding a point in an infinite space

Instead, project the infinite plane on a finite one using any bound analytic function like for example ArcTan. For whole numbers this should be as fast as warty goblin's algorithm, since it also uses splitting the plane in halves regarding the specific digits in binary representation.

By using more general questions and slicing the scaled down infinite plane in a natural geometric way, one can approximate any sought number much faster and obtain any desired precision in finite time even if we consider any real number pairs. Cosidering how real numbers are constructed as a limit of rational sequences, we will also obtain exact result in countable infinite questions as well.
Let's be clear here though, the number of questions required to reach a desired precision (in the original infinite space) depends on the point being sought. You can't say, give me an epsilon, and I will give you an N that will work for all (x,y) points. After N questions there are some points that share all answers with points arbitrarily larger.

13. Re: Finding a point in an infinite space

Originally Posted by DavidSh
Let's be clear here though, the number of questions required to reach a desired precision (in the original infinite space) depends on the point being sought. You can't say, give me an epsilon, and I will give you an N that will work for all (x,y) points. After N questions there are some points that share all answers with points arbitrarily larger.
That is true. Still for any given number x, the number of questions needed is of order Log(x).

14. Re: Finding a point in an infinite space

[Merging a couple of cases given above and hopefully being a bit more explicit. Radar pretty much said the first 2 paragraphs, while the uncountable case was mentioned by Davidsh ]

For something like the integers. If you have an finite range (x), you are never going to get better than Log2(x) on average, as that differentiates at most x numbers. On the other hand you can get the exact number in Log2(x) via fairly trivial methods (binary chop)

You can trivially get the upper bound for a number (y) in the same time by working upwards, if you use faster growing strategies you save time here, but then your upper bound is crazily high (and the lower bound crazily low), I suspect there are ways to optimize that.

IIUC the binary expansion given by Warty Goblin didn't explicitly terminate, but actually that might be the most efficient way round. Explicitly asking if you finish will get you the number in exactly Log2(x) but if you use a probabilistic approach so you only ask after a suspicious amount of zeros you could probably get much closer to Log2(x).

For a plane you can basically do the 2 co-ordinates separately. You could probably save some steps by finding the (approximate) hypotenuse and then the smallest co-ordinate.

Fractions get a bit more awkward. Treating X/Y as X,Y will of course work, or alternatively (and possibly more elegantly) continuing the binonial chop the other way until it's confirmed as repeating. But it feels (as a non-serious-mathmo) ugly. In the integer case, the bigger number takes a little more time, but it's a much bigger number so you'd expect it too. Anything better than linear seems reasonable too me. In the fractions case between any two fractions, there will be a fraction that will take a (countably) infinite amount of time to resolve but is also infinitesimally close.

Irrational numbers, even a countably-infinite number of separations leaves an uncountably-infinite set of numbers in at least one 'box'. You could get arbitrarily close by continuing binary chop.

Fairly given computational numbers I think I'd do binary chop for a decent while, then see if I can recognize it (doing some unofficial questions of my own). If sqrt[2]+10-1000 is fair game then I don't see a sensible way out unless there are clear limits. [ETA revised credit statements, and also in this case I'd ask them to write it down in words then build up the sentence letter by letter-sorted!!

[10th Edit, Warty Goblin's method does of course include a termination. But not in the bits he repeats :sillyme:

15. Re: Finding a point in an infinite space

Originally Posted by jayem
Irrational numbers, even a countably-infinite number of separations leaves an uncountably-infinite set of numbers in at least one 'box'. You could get arbitrarily close by continuing binary chop.
Actually even in continuum interval (or plane - doesn't matter) you can get an exact number after countable infinity of binary chops, since this is a consequence of the very definition of real numbers - more specifically the construction from Cauchy sequences. Getting arbitrarily close after countable infinite steps becomes an exact solution.

16. Re: Finding a point in an infinite space

Actually even in continuum interval (or plane - doesn't matter) you can get an exact number after countable infinity of binary chops, since this is a consequence of the very definition of real numbers - more specifically the construction from Cauchy sequences. Getting arbitrarily close after countable infinite steps becomes an exact solution.
Yes. Unfortunately, if each question takes finite time to ask and answer, there is no such thing as "after" a countably infinite number of steps.

17. Re: Finding a point in an infinite space

I set the origin at -X, -Y away from a chosen spot, declare that I have thus found the exact point required, and take the trophy (I assume there's a trophy involved) for finding it in 0 questions.

18. Re: Finding a point in an infinite space

Originally Posted by AvatarVecna
There is a plane where the X-axis goes from -∞ to ∞ and where the Y-axis goes from -∞ to ∞. You know that somewhere on the plane is a point whose X and Y values are both whole numbers. Your goal is to find this point, but you can only ask yes/no questions about the point; there's no limit on how many such questions you can ask, nor on the complexity of the questions, save that they must be answerable with a binary "yes" or "no" answer. Can you find the point, and if so what is your method?
Originally Posted by tyckspoon
Pretty easy; "is the y coordinate greater than 0?" Repeat for x. Now you know which quadrant it's in. Repeat basically the same questions, increase the number you ask about by.. Oh a billion or so until you get a broad zone to narrow into. There's probably a more efficient algorithm, but it's not hard to do.
We already know which quadrant it's in; they're whole numbers, so they must be a positive integer or 0. No other quadrant is possible, unless the OP is edited to say "the absolute value of their X and Y values are whole numbers."

19. Re: Finding a point in an infinite space

Originally Posted by Mark Hall
We already know which quadrant it's in; they're whole numbers, so they must be a positive integer or 0. No other quadrant is possible, unless the OP is edited to say "the absolute value of their X and Y values are whole numbers."
According to Wikipedia whole numbers are integers and can de negative. Natural numbers are the ones that must be positive.

20. Re: Finding a point in an infinite space

Originally Posted by AvatarVecna
That such a method can theoretically work for a vast number of points is obvious, but it runs into issues because of the nature of the infinite plane.
If the potential number of questions is infinite as well most if not all of those issues should be negated in theory, shouldn't they?

EDIT:
Now that I think of it, maybe not. If the space is continuous then the number of points is uncountably infinite whereas the number of questions must be countably infinite. It should work in an infinite grid of integer coordinates though

21. Re: Finding a point in an infinite space

Originally Posted by Bohandas
If the potential number of questions is infinite as well most if not all of those issues should be negated in theory, shouldn't they?

EDIT:
Now that I think of it, maybe not. If the space is continuous then the number of points is uncountably infinite whereas the number of questions must be countably infinite. It should work in an infinite grid of integer coordinates though
With countable infinity of questions one can still pinpoint a... well... point within the continuum. It is the basic concept behind the very construction of real numbers in the version by Cauchy where a real number is defined by a class of convergent sequences, which also are convergent if you essentially mix them up with each other.

With the yes/no questions one finds and refines upper and lower bound for the sought number. Subsequent values of those bound form a sequence. Since we can assure that there is always a finite number of questions we need to make our precision arbitrarily good, then those upper and lower bound sequences converge to a single real number.

22. Re: Finding a point in an infinite space

Originally Posted by jayem
For a plane you can basically do the 2 co-ordinates separately. You could probably save some steps by finding the (approximate) hypotenuse and then the smallest co-ordinate.
Would that be equivalent to a graphical method where you start by asking if it's a solution to the inequality y>0 and then go on to define smaller and smaller regions using systems of inequalities? It seems like it would be simple to divide each existing half of the graph in half again using that sort of method and various y>mx type equations. This method seems interesting to me because your guessing keeps narrowing the search space while telling you very little about how far away either coordinate is from the origin (since we're only considering integers, we do gradually eliminate coordinates closer to the origin as no integer coordinates are found within that particular narrow slice).

23. Re: Finding a point in an infinite space

Originally Posted by Algeh
Would that be equivalent to a graphical method where you start by asking if it's a solution to the inequality y>0 and then go on to define smaller and smaller regions using systems of inequalities? It seems like it would be simple to divide each existing half of the graph in half again using that sort of method and various y>mx type equations. This method seems interesting to me because your guessing keeps narrowing the search space while telling you very little about how far away either coordinate is from the origin (since we're only considering integers, we do gradually eliminate coordinates closer to the origin as no integer coordinates are found within that particular narrow slice).
I was thinking about methods like that, and how to extract information about the distance from the origin. An algorithm I had considered was something like this:

1: wlog, assume the point is in the first quadrant, since it only takes two questions to determine this.
2: ask if the point is above the line bisecting the quadrant. Regardless of the answer, you now have contained the point between two known rays at unknown distance. Call the lower ray r1 and the upper r2
3: Ask if the point is contained in a triangle determined by r1,, r2, and a line defining an isosceles triangle defined by r1 and r2 with the congruent legs of length, say, k!, where k is the number of questions you have asked.
4: If the answer is yes, exhaustively search the whole number pairs in the triangle.
5: If no, return to step 2, and bisect the angle determined by r1 and r2.

There's probably an additional way to make it clever, by trying to learn something about how far to jump, I just chose k! because it grows quite quickly, but it may be more efficient in some sense to pick a growth value that keeps the number of points in the triangle reasonably constant.

24. Re: Finding a point in an infinite space

Er, how exactly does one bisect an infinite plane?

25. Re: Finding a point in an infinite space

Originally Posted by georgie_leech
Er, how exactly does one bisect an infinite plane?
Right down the middle.

More seriously: what I think they're proposing is to ask if the point on the plane is above or below the line y=x. Let's assume its below y=x. Knowing this, we can form a triangle using y=x, the x axis (y=0), and the line y = -x + k!, where k is the number of iterations. Eventually the point will be contained by the triangle, and we can search the remaining space.

It's essentially the same as asking about the sum of |x| and |y| to constrain both x and y within some search space at the same time.

Since any number can be expressed through a unique prime factorization, another approach would be to ask about the prime factors of X and Y. From what I can tell from some back of the napkin scribbles, the best case could be reasonably fast, but the worst cases crawl to a snails pace.

EDIT: I didn't actually answer the question.

Bisecting an infinite plane is easy: any line on an infinite plane bisects that plane. If that sounds confusing, think of it this way: there is a one to one mapping for every point on one side of the line to a point on the other side (reflection over the line being the simplest mapping I can think of).

26. Re: Finding a point in an infinite space

The infinite 2D plane just complicates things. So get rid of that first. Draw a continuous square spiral starting at the origin:
(0, 0)
(1, 0)
(1, 1)
(0, 1)
(-1, 1)
(-1, 0)
(-1, -1)
(0, -1)
(1, -1)
(2, -1)
etc.

This line goes through all points (x, y) on the infinite plane, mapping them to position n an infinite line with n ≥ 0.

From there the trick of asking for each binary digit of n is more obvious, and I don't see any way of making it faster.

Edit: you can do this with a real number plane as well. Space-filling curves are a lot of fun. I think the step of asking for binary digits won't work the same for real numbers, as a finite irrational number will have an infinite number of digits after the decimal point, and no repeating pattern to them.

27. Re: Finding a point in an infinite space

Originally Posted by Algeh
Would that be equivalent to a graphical method where you start by asking if it's a solution to the inequality y>0 and then go on to define smaller and smaller regions using systems of inequalities? It seems like it would be simple to divide each existing half of the graph in half again using that sort of method and various y>mx type equations. This method seems interesting to me because your guessing keeps narrowing the search space while telling you very little about how far away either coordinate is from the origin (since we're only considering integers, we do gradually eliminate coordinates closer to the origin as no integer coordinates are found within that particular narrow slice).
I think so, but I did it the other way round.

This I think has the potential to save some steps. Rather than having to do 2 rangefinder operations you only have to do 1.
So using doubling the descartes method takes log(X)+log(X)+log(Y)+log(Y) steps whereas the polar method takes about log(1.4*X)+log(1.4*X)+log(1.4*2P*X)

If X is about the same as Y you get 4 log(X) against 3 log(X) +C . (If Y is negligible you get 2 log (X) against 3 log(X) so it does lose out on the extreme edges)
However I think you can do rangefinding a bit better than that.

I think my way round (distance first) is slightly better than angle first as when you know the distance you know how many points are in the ring/diamond so you know when to stop (although alternating would be quite possible). I think to get the binary places to use diophantime equations would require as many steps as it saves.

The space filling curve looks like it may be even better to me than that, at first thought. Again you get the single range.

28. Re: Finding a point in an infinite space

Originally Posted by georgie_leech
Er, how exactly does one bisect an infinite plane?
You get arbitrary.... sort of like Star Trek, actually.

The Terran System is Sector 001. There's no particular REASON for it to be 001; if they started at the galactic core, our sector would be far higher. But, they picked an arbitrary point (where they were standing) and declared that to be the center of their coordinate grid.

If I say "This point I occupy is 0,0,0 on an xyz coordinate space, pointing to X, Y, and Z, and defining the length of an integer of distance in that space, I can then define other objects in that X,Y,Z space, regardless of any other arbitrary system. My coworker's chair is 2,0,0, since it is 2 meters ahead of me, and neither right nor left nor above or below me. It is a purely relational statement... but if you're looking for a point in space, you've at least cut the infinity you had to search into 8, smaller, infinities.

29. Re: Finding a point in an infinite space

Originally Posted by Mark Hall
You get arbitrary.... sort of like Star Trek, actually.

The Terran System is Sector 001. There's no particular REASON for it to be 001; if they started at the galactic core, our sector would be far higher. But, they picked an arbitrary point (where they were standing) and declared that to be the center of their coordinate grid.

If I say "This point I occupy is 0,0,0 on an xyz coordinate space, pointing to X, Y, and Z, and defining the length of an integer of distance in that space, I can then define other objects in that X,Y,Z space, regardless of any other arbitrary system. My coworker's chair is 2,0,0, since it is 2 meters ahead of me, and neither right nor left nor above or below me. It is a purely relational statement... but if you're looking for a point in space, you've at least cut the infinity you had to search into 8, smaller, infinities.
But you'very already done that with the origin though, no? After narrowing it down to one of the 4 regular quadrants, you've effectively set boundaries that prevent proper bisecting. There will always be more of the infinite plane on the side opposite your line, so it's not halving anything, so much as dividing an area into 2 arbitrary pieces.

30. Re: Finding a point in an infinite space

Originally Posted by georgie_leech
But you'very already done that with the origin though, no? After narrowing it down to one of the 4 regular quadrants, you've effectively set boundaries that prevent proper bisecting. There will always be more of the infinite plane on the side opposite your line, so it's not halving anything, so much as dividing an area into 2 arbitrary pieces.
Setting that initial quadrant boundary is your act of bisecting infinity. You get one.

After that, you have to sound things out, with "Is [x,y,z] less n", per the OP's "Infinite Yes/No questions"

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•