Math Quiz Three

This challenge is to produce a function y = f(x) with the following characteristics (and to prove that it has them):

It must be single-valued for all real x at which it is defined.
It should be definable in finite space with formulae and/or words (in case anyone has any clever meta-functions in mind).
There exists at least one point in its graph (on the standard Cartesian x-y plane) within every possible circle of positive radius whose center's y-coordinate is on the interval [0,1). (That's 0 included, 1 excluded.)

Such properties as differentiability, integrability, continuity, periodicity, or everywhere-definedness are not required.
Give answers below the triple horizontal rule below. (Please give names so we can keep up with you.) Responses will be posted alongside.
Extra points if (in Characteristic #3) one can broaden the interval for y (even to (-inf,inf) if you can).
Hints and clarifications will be posted below as comments or submissions suggest.
I do have a solution (although I make on it no claims of superiority); provide an email address in a comment and I will probably provide (particularly if you've commented and/or submitted before!).
This MathQuiz the fault of DavisHerring?.

Clarifications:

For every such circle that can be specified (X,Y,R), you must be able to show that there exists a point (x,y) such that the distance from (X,Y) to (x,y) is less than R and f(x)=y.

Those who have solved the puzzle:

VickiKerr

Comments:

Hey... you expressly prohibit functions not "definable in finite space with formulae and/or words" in order to prohibit clever "meta-function" tricks. I'm interested! What are these "meta-function" things which are so difficult to define, and where would I find a source where I could read up more on them? -- MichaelChermside

I didn't have something particular in mind; any description that one would terminate with 'and so on' is the closest I can think of. "This function is periodic with period 1, and is defined at a random value at 1, and a different random value at 1/2, and different random values at 1/4 and 3/4, and more random values at the intervening eighths, and so on." I wanted a function which fulfilled the criteria by a non-trivial mechanism. Anyone with ideas and/or resources want to start a MetaFunction? page? -- DavisHerring?

Below here lie what may be spoilers! Proceed with caution.

Hints: None so far.

Submissions:

sin(1/x) for x non zero. 0 for x zero

(1/x)sin(1/x) to go close to the whole y axis

These functions don't pass through the circle centered at (1/pi,.9) with radius .01, since they're close to 0 there. And please put names to your submissions! -- DavisHerring?

[What? Why does it have to pass through that circle? It is not centered somewhere on the y axis as you requested. Do I not understand the puzzle? It seems to me like these functions solve the problem (in original and "bonus" form, respectively. Oh, okay, it is a little misleading. You mean that the center of the circle is in {(x,y) | y is in [0,1)}. There are no restrictions on the x value of the circle. It sounded a little like you wanted the center of the circle to be in {(0,y} | y is in [0,1)}.]

[Did it? The original description gives "whose center's y-coordinate is on the interval [0,1)". No mention is made of the x-coordinate, so it is purely your own imagination which led you astray. -- vk]

[My, aren't you sour, vk. Yes, it did sound a little like what I said, and apparently not just to me. Whenever a person is misled, it is a combination of what they are reading and their process of reading it. If it was "purely one's imagination", it would be something more like a total hallucination. If one reads Davis's requirements carefully, one will not get the wrong idea, so getting the wrong idea, if blame is to be apportioned, as you seem to want to do, would indeed be the fault of the reader. But I think it is easy to get the wrong idea, and as an example, the person who offered the above solution obviously did, since his answer solves the problem as I first read it. Anyway, the first comment should never have been added -- let's delete it, and what it generated.]

Wait a minute, it said all possible circles, which certainly includes {(0, y} | y is in [0,1)} as a subset. -- DougMerritt

Let's try f(m/2^n) defined as p/q if and only if the following all hold:

p, q are positive coprime integers such that p/q is a proper fraction
m and p are odd integers
n = p * 2^q

I haven't checked this carefully, but hopefully it works. If q is a large enough prime, p and m can be chosen so that the point (m/2^n, p/q) is close to the point (X, Y). -- VickiKerr

I thought about it a while, and it seems to check out. What's more, it's easily extended to the rest of the plane, and is more elegant than my solution (although I would argue that mine is more straightforward). Bravo. -- DavisHerring?

I can't quite prove this will work, but my idea is:

f(m + p/q) = (p * 10^-n) * 10/9 - 1/9 iff

m is integer
p and q are positive coprime integers where p/q is a proper fraction
n is the number of digits in p, which assures that (10^-n * p) is in the range [.1, 1)

Then consider a point X,Y (Y on [0, 1) ) and show we can get arbitrarily close to it. Consider the series y1, y2, y3... of integers constructed from Y such that yi is the integer part of y*10^i; and the series x1, x2, x3... of integers such that xi minimizes the value of (fractional part of X) - yi/xi. By using values (p,q) = (yi, xi), it should be possible to show that a large enough i lets us get arbitrarily close to X,Y. Getting close in the Y direction is obvious from the construction; proving we can *simultaneously* get close in the X direction (in such a way that the total distance is always asymptotic to zero and not some positive value) is the tricky part.

-- KarlKnechtel

(I assume that by "xi minimizes the value of (fractional part of X) - yi/xi" you mean that xi minimizes the absolute value of that expression.)

First you have p and q as coprime positive integers with p<q -- this is useful, because it guarantees that all pairs of p and q will have a unique ratio, thus making your function single-valued as required. (This was presumably VickiKerr's reason for using it!) However, you have no way of guaranteeing that the p and q values you generate are coprime.

That part's fine I think. For any non-coprime p1 and q1, there will be coprime p2 and q2 that correspond to the same X value. I mean to use that p value when evaluating f(x). I would normally use a phrase like "in lowest terms", but I was copying the idiom from above.

Secondly, if X is exactly an integer, this function may well pass arbitrarily close to (X,Y), but your expansion is not well defined then. Since the fractional part of X is zero, minimizing the value of abs(fpart(X)-yi/xi) means making xi as large as possible. This allows no specific answer.

Er, yes, I'd need f(x) not to be defined at exact integers I guess. The original problem statement said we don't require continuity. The function is defined for enough values close to the exact integers to satisfy the requirements. I think.

Moreover, consider (X,Y)=(0.1,0.1). Then the sequence of yi values will be 1, 10, 100, etc., and the sequence of (p * 10^-n) values will be {0.1,0.1,0.1,...}; the sequence of xi values will be {1,1,1,...}, to minimize abs(0.1-0.1/xi). This means that the sequence of points (m+p/q,f(m+p/q)) will be (m+0.1,0.1*10/9-1/9); taking m=0, we have (0.1,0). This unfortunately does not converge to (0.1,0.1).

Ecch. In this case we don't get to converge properly, because we're not *approaching* the X coordinate - we start at it. That happens for any rational X value, I imagine. The "minimize" bit up there has to be modified to exclude making the value equal to zero. That should be sufficient... ?

I'm not saying your function does not solve the puzzle, but your argument does not establish it as a solution, and that is required as well. -- DavisHerring?

Indeed. Maybe someone else can make something more solid out of this. Thanks for your points, anyway. -- KarlKnechtel

GarethMcCaughan says: It's enough if there's a point in each C(x,y,r) where x,y,r are rational. There are only countably many of these. So, enumerate them. Then stick a point in each.

That's not very explicit, but it's easy to make it so. On the other hand, it's also painful, so I shan't :-). But I think this is probably the easiest way to see that there must be a solution. It obviously extends to the whole of the plane, too. Vicky's elegant solution is, so to speak, an instantiation of this template.

That would be enough, since for C(x,y,r) you can always have a smaller, rational, r and then pick rational (x,y) nearby, and then any point in that circle is inside the first. And it may in fact guarantee a solution, since you then have the density of the real numbers to bring to bear on a puny countably-infinite set. But any solution that relied on this would risk running afoul of the "meta-function" clause; it's a bit ContentFree? to say that "and it gets all the rest of them because there're only AlephZero? of them". -- DavisHerring?

That's why I said "That's not very explicit, but it's easy to make it so". Enumerating tuples of rationals and integers explicitly isn't terribly hard, and that's basically all you need. So the meta-function clause can be avoided. I'm not going to do it, though, because it's tedious :-). -- GarethMcCaughan

You haven't stated how you ensure the function is single-valued. -- vk

Taking quick inspiration form Gareth, - thanks Gareth. Here's an easy way to define it: for every pair of points in the specified band - R x [0,1) -, with rational coordinates ((x1,y1), (x2,y2)) take the weighted average : ( (x1+pi*x2)/(1+pi), (y1+pi*y2)/(1+pi)) to be in the graph of the function, for the rest of x coordinates pick anything like 0. If the function is not single valued then pi is rational, then in every circle we talk about there will be 2 points with positive rational coordinates, therefore their weighted average is also in the circle, and is by definition a part of the function's graph. -- CostinCozianu

As it stands, that's not single-valued (consider what happens if y2 is replaced by y3). -- vk

Thanks, Vicki. That's what happens when doing math in lunch breaks - you get dizzy. :) Refactored solution:

  from the pair of points [P1:(x1, y1), P2:(x2,y2)] of rational coordinates with (a) x1 < x2 and y1 < y2

we derive the point P:(x,y) where

  x= (x1+x2)/2 + pi * (x1-x2) + (pi^2)*y1*(y1-y2)+(pi^3)*(y2-y1)
  y= (y1+y2)/2

Now assume we have 2 distinct points P and P' having the same x coordinate, then we derive a polynomial over Q that has pi as root, but pi is not algebraic over Q so the polynomial must be 0; therefore we derive that:

   x1' + x2'  = x1 + x2 
   x1' - x2'  = x1 - x2
   y1' - y2'  = y1 - y2
   y1' (y1' - y2')  = y1 (y1-y2)

Given also (a) it follows that x1= x1', x2=x2', y1=y1', y2= y2'

So we can't have a multi-valued function, we put all these points that are also within the 0<=y< 1 range in the graph. Now for every circle in that domain let's say with diameter d, we can find 2 points P1 and P2 with the properties above situated in a circle with the same center but with diameter d/1000 -> |x1-x2| <d/1000 and |y1-y2|<d/1000 and the distance from the center to P1, P2 is also less than d/1000. It can be derived easily that the point P derived as above (therefore in the function graph) is within the circle of diameter d. For circles whose interior fall in part outside the 0<=y<1 band so our P may be outside the [0,1), we take a circle with diameter d/2 that falls within the band and find the point P in a similar way. -- Costin

(Anyone have other approaches?)

Surely this is misphrased; consider condition #3, with circles taken with arbitrarily small radius; this essentially sweeps out the line x=0 and its neighborhood, yet it is required to be single-valued. Impossible; only the line segment x=0, y=[0,1) can satisfy this, yet that is multi-valued. -- DougMerritt

I think this is really possible, condition #3 is just saying you cannot fit any circle, however small, centered on the y in [0,1) interval without circling any points of the function. For a 1-D analogy, consider the function y = f(x) = 1 if x is rational, =0 if x is irrational. It will sweep very densely through both y=0 and y=1, i.e. you cannot find a finite interval on either y=0 or y=1 line that has no point satisfying f(x). If you can spread this thing out dense enough in 2D, you have solved the quiz. My initial guess to take f(x) as some decimal part of x, so it spreads densely thoughout, but haven't figured out the details yet. -- OliverChung

Submission

Got it, I use

  y = f(x) = 0 if x is a non-terminating decimal,
           = 0.[reversed sequence of digits of x] otherwise.
  i.e. if f(123.456) = 0.654321.

Proof

Given any (X,Y,R), Y in [0,1). Pick r in (0, R) such that Y + r < 1 and the square (X +/- r, Y +/- r) is completely inside the circle (X,Y,R), r always exists since Y<1 and R>0.
Pick y1 in [Y, Y+r) s.t. y1 is a terminating decimal, such as taking Y+r and truncating after enough decimal points, always possible since r>0.
Define dx = reverse sequence of digits of y1, with 0. and [10 + # of 0's before r's first digit] 0's prepended, so we have dx < r.
Pick x1 = X + dx, therefore x1 is in [X, X + r]
f(x1) = y1 + dy by construction of (2), dy < r by construction of (3), therefore f(x1) is in [Y, Y + r], so the point (x1, f(x1)) is within the circle (X,Y,R) by construction in (1).

-- OliverChung

CategoryMath