Wikipedia:Reference desk/Archives/Mathematics/2013 March 26

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 26

Perspective correct interpolation of screen coordinates given desired texture coordinates on a plane

File:Iterpolation of screen coordinates based for given texture coordinates.png

Interpolation of screen cordinates for given texture coordinates (lower frame), initially given only four correspondences (upper frame).

I'm looking for a simple formula to allow perspective correct interpolated 2D screen cordinates to be calculated for given 2D texture coordinates, given that a 3D projection, distortionless camera is looking at a plane. Specifically, I don't know anything about the camera position, orientation or field of view (and I don't care about it directly) and I only have some reference points. It needs to be as fast as possible to solve.

The article on texture mapping shows the opposite: perspective correct interpolated 2D texture coordinates (U, V) given the 2D screen coordinates (X, Y).

Here is the problem described exactly:

Input: Four corresponding screen and texture coordinates (four sets of (X, Y) coordinates and four sets of corresponding (U, V) coordinates)

Output: A function that, given (U, V), it generates the appropriate (X, Y) coordinate, exact if the camera is distortionless.

I would also settle for the solution where the input (U, V) values are limited to (0, 0), (0, 1), (1, 0) and (1, 1). Eonzo (talk) 14:25, 26 March 2013 (UTC) Eon

If you don't supply the 4 corner points, and thus are doing extrapolation, then the error in the calculations will tend to magnify, the further outside the inputs you go. The problem is also simpler if 2 pairs of input coords vary only in U, and 2 pairs vary only in V.

I also note that your intermediate grid lines are not evenly spaced. This is correct in a perspective view, but does complicate the math. Would you settle for evenly spaced grid lines ? That is, where we can just linearly interpolate between the inputs ? (If we can't take this shortcut, then we'd probably do best to calculate the camera angles from the inputs, which could mean that many sets of inputs would fail to converge on a solution, and others would have multiple solutions. Very messy. Note that in the top pic, we can't tell which corner is closest, since that info isn't present, but we've added that info with the spacing of the grid lines in the 2nd pic, meaning we've added info not present in the input. If we spaced the grid lines further from the lower, right point, then that point would appear to be the closest.) StuRat (talk) 15:22, 26 March 2013 (UTC)

The simple linearly spaced case is easy but that is not what I am generally interested in. I think that any ambiguities will "cancel out". Lets consider the simple case of a 1x1 square in (U, V), with the origin as one corner. The only ambiguity in the top pic is which side of of the plane the camera is, but the two possibilities will have the same results when used to interpolate. There are some impossible cases, such as having three points colinear and a fourth offset. Finally, when the camera is looking orthogonal to the plane then there are infinitely many solutions for camera position, but again it doesn't matter becase they all reduce to the simple linear interpolation case. This is why I stress that I don't care about any information other than the interpolating function. 105.236.8.206 (talk) 18:19, 26 March 2013 (UTC) Eon

Alternate interpolation grid lines using same corner coords as above.

If I interpret you correctly, that linear grid spacing is not what you want, then why do you say "the two possibilities will have the same results when used to interpolate" ? Won't the largest grid square be near whichever side of the figure is meant to be closer to the viewer, meaning different interpolation will be used for these ambiguous cases ? StuRat (talk) 18:53, 26 March 2013 (UTC)

I'm not 100% sure but while the two cases will have significantly different meanings in 3D, the lower left corner in the top figure is always the nearest point and the (X, Y) coordinate interpolated for say (U, V) = (0.5, 0.5) will be the same in both cases. Or any such texture coordinate. I THINK the furthest point will always have the largest internal angle or the furthest edge will always be shortest in screen coordinates. The necessary information seems to be in the four reference points. My logic could be flawed but it feels instinctively right. 105.236.8.206 (talk) 19:35, 26 March 2013 (UTC) Eon

Isn't this illustration also a valid interpolation of the U = 0.5 and V = 0.5 grid lines ? StuRat (talk) 23:21, 26 March 2013 (UTC)

No, not if the assumptions are what I think they are. Lines project to lines, so (0.5, 0.5) can only be at the intersection of the line segments connecting opposite corners of the projected square. Projected parallel lines meet at a point (if not still parallel), so the line V=0.5 can only be the line containing the center point and the intersection of the extended top and bottom edges. You can find U=0.5 in the same way and subdivide from there. So there is a unique solution. I'm not sure about the most efficient way to calculate it. -- BenRG (talk) 04:29, 27 March 2013 (UTC)

The original image provided by the OP doesn't have the (0.5, 0.5) point at the intersection of the line segments connecting opposite corners (it's lower and to the right). It's closer than in my version, but not quite there. And, if we did find it that way, wouldn't that just be the linear spacing of grid lines I suggested earlier ? StuRat (talk) 04:42, 27 March 2013 (UTC)

Yeah, my image was created by hand, so not quite perfect, but I agree with BenRG. (0.5, 0.5) would be the point at the crossing of the two diagonal lines. Thereafter, relying on the fact that parallel lines meet at the same point, one can use the pink or teal lines in step 3 of the small image to uniquely define the lines U = 0.5 and V = 0.5 (I have two points on each). This process can then be repeated to split the square into arbitrarily small units. This at least illustrates that the interpolation is unique given the four points (even if the camera position in 3D isn't iniquely determinable). Eonzo (talk) 07:47, 27 March 2013 (UTC) Eon

Oh, and no StuRat, the simple linear case will make the line U = 0.5 cut two of the edges exactly in half (as measured in screen coordinates or pixels), but this is not generally the case. Even in my inaccurate picture it should be apparent that that line is closer to the farthest point (again, in screen coordinates). Eonzo (talk) 09:29, 27 March 2013 (UTC)

OK, we could always repeat that construction method as many times as needed to find the desired U and V. However, it won't work in the case of parallel lines (where there is no intersection), or where they are very close to parallel (since the coords of the intersection will be too large and we will get an overflow error). Can the angle of each U or V line be determined in proportion to it's distance (either in terms of U,V or X,Y) ? That is, if we have a U line 1/3 or the way from a U line with an angle of 0 and 2/3 of the way from a U line with an angle of 15, does that mean the new U line has an angle of 5 ? If so, this would simplify calculations.

As far as the spacing goes, if the U = 0.5 line isn't halfway between the U = 0 and U = 1 lines, then it's distance between them ought to be a function of the unit (X,Y) lengths of the U = 0 and U = 1 line segments, right ? If you can provide some actual data, we might be able to determine just what that function is. StuRat (talk) 15:39, 27 March 2013 (UTC)

You can avoid special cases by working in projective coordinates, which have the nice property that if P and Q are points, the line containing them is P×Q (the cross product), and if L and M are lines, their point of intersection is L×M. So if A, B, C, D are the corners in circular order, the center point is (A×C)×(B×D) and the line U=0.5 (or V=0.5) is ((A×C)×(B×D))×((A×B)×(C×D)). I don't know how to turn this into an efficient algorithm, though. -- BenRG (talk) 21:32, 27 March 2013 (UTC)

Illustration that simply using the "lines project to lines" fact, the unique interpolation can be iterated to arbitrarily fine scale.

• The standard algorithm is explained at Texture mapping#Perspective correctness. Looie496 (talk) 16:34, 26 March 2013 (UTC)

No that answers the inverse question. I guess I can probaly try and start from there and try to turn it around. Could it be that the same formula applies in both cases.... 105.236.8.206 (talk) 18:25, 26 March 2013 (UTC) Eon

• I'd think we could do better than the "affine" version displayed at that link, even without knowing depth info, like so:

      +-+-+
     /  |  \
    /---+---\
   /    |    \
  +-----+-----+

I see no reason why the grid lines can't all be straight, even if we do lack depth or camera placement info. We do, however, still have the problem of how the grid lines are spaced, as I mentioned above. StuRat (talk) 17:08, 26 March 2013 (UTC)

You might be interested in my answers to a similar question here: Wikipedia:Reference_desk/Archives/Computing/2012_April_18#how_hard_is_2.5_d. While not a direct answer to this Q, it contains examples of factors you may not have considered, like to need to distinguish between foreground and background pixels, and the need to reduce the thickness of more distant lines, or change their darkness, to simulate this effect. StuRat (talk) 18:56, 26 March 2013 (UTC)

You might want to investigate Inverse perspective mappings. There is extensive literature on the subject. This paper [1] is a good starting point.--Salix (talk): 15:31, 27 March 2013 (UTC)

You can consider the projection as a map from 3D to 2D. If (x,y,z) is a point in 3D then the image (X,Y) will be (x/z,y/z). Consider a parallogram in 3D with vertices ${\vec {a}},\ {\vec {b}},\ {\vec {c}},{\vec {d}}$ Let ${\vec {u}},\ {\vec {v}}$ be vectors along the two edges so ${\vec {b}}={\vec {a}}+{\vec {u}},\ {\vec {c}}={\vec {a}}+{\vec {v}},\ {\vec {d}}={\vec {a}}+{\vec {u}}+{\vec {v}}$ and a point with texture coodrinates (s,t) will be ${\vec {a}}+s{\vec {u}}+t{\vec {v}}$. Now the four corners map to the known 2D points ${\vec {A}},\ {\vec {B}},\ {\vec {C}},\ {\vec {D}}$. If we can find the vectors ${\vec {u}},\ {\vec {v}}$ then we have effectively solved the problem. Without loss of generality set ${\vec {a}}=(0,0,1)$ and A=(0,0). Let ${\vec {B}}=(B_{x},B_{y})$ and ${\vec {u}}=(u_{x},u_{y},u_{z})$ etc. so ${\vec {b}}=(u_{x},u_{y},1+u_{z})$ We now have a set of equations

File:Perspective correct screen coordinate interpolation illustrated.png

Screen coordinates for green points, linear in texture coordinates, could be easily found from the black reference points after linearization of the problem.

${\begin{aligned}B_{x}&=u_{x}/(1+u_{z})\\B_{y}&=u_{y}/(1+u_{z})\\C_{x}&=v_{x}/(1+v_{z})\\C_{y}&=v_{y}/(1+v_{z})\\D_{x}&=(u_{x}+v_{x})/(1+u_{z}+v_{z})\\D_{y}&=(u_{y}+v_{y})/(1+u_{z}+v_{z})\\\end{aligned}}$

or more simply

${\begin{aligned}B_{x}*(1+u_{z})&=u_{x}\\B_{y}*(1+u_{z})&=u_{y}\\C_{x}*(1+v_{z})&=v_{x}\\C_{y}*(1+v_{z})&=v_{y}\\D_{x}*(1+u_{z}+v_{z})&=u_{x}+v_{x}\\D_{y}*(1+u_{z}+v_{z})&=u_{y}+v_{y}\\\end{aligned}}$

This give 6 equations in 6 unknowns $u_{x},\ u_{y},\ u_{z},\ v_{x},\ u_{y},\ u_{z}$. Which you can solve by your favorite method.--Salix (talk): 17:08, 27 March 2013 (UTC)

Solved! Thanks, you linearized the problem nicely, so I used Gauss-Jordan elimination on a 6x6 matrix (done once per four input points, fairly efficient) and therafter interpolation is very quick. Image on the right was generated by my program. It susprises me somewhat that the sytem isn't singular in the case where the opposite edges are parallel or even if the screen coordiantes form a perfect square. I would have guessed that this case would have had to be handled special, but it seems to work fine. Perhaps this comes from allowing ${\vec {u}}$ and ${\vec {v}}$ to not be orthogonal? Eonzo (talk) 19:59, 27 March 2013 (UTC)

If you think about it the simplest example would be if the source is square in the plane z=1. The sides will be parallel in the source and as they have the same z-value also parallel after projection. The mapping in this case is a trivial calculation. Indeed parallel sides mean $u_{z}=0$. I guess singularities are avoided as we don't need to actually calculate vanishing points. Are ${\vec {u}}$ and ${\vec {v}}$ orthogonal? I'm not sure what the condition for this to happen is.--Salix (talk): 22:11, 27 March 2013 (UTC)

In my mind I've been visualising, at least for the case of a 1x1 texture, a square texture region and not a parrallelogram. Is your solution the general case allowing any (U, V) coordinates with the reference points? For now I'll treat your solition as a useful black box but I really need to think about it more. Thanks a lot for putting in so much work helping me out. Eonzo (talk) 07:07, 28 March 2013 (UTC)

You might be able to make it even easier. Writing the second set of equation as a matrix

${\begin{pmatrix}1&0&-B_{x}&0&0&0\\0&1&-B_{y}&0&0&0\\0&0&0&1&0&-C_{x}\\0&0&0&0&1&-C_{y}\\1&0&-D_{x}&1&0&-D_{x}\\0&1&-D_{y}&0&1&-D_{y}\end{pmatrix}}{\begin{pmatrix}u_{x}\\u_{y}\\u_{z}\\v_{x}\\v_{y}\\v_{z}\end{pmatrix}}={\begin{pmatrix}B_{x}\\B_{y}\\C_{x}\\C_{y}\\D_{x}\\D_{y}\end{pmatrix}}$

Swaping columns gives

${\begin{pmatrix}1&0&0&0&-B_{x}&0\\0&1&0&0&-B_{y}&0\\0&0&1&0&0&-C_{x}\\0&0&0&1&0&-C_{y}\\1&0&1&0&-D_{x}&-D_{x}\\0&1&0&1&-D_{y}&-D_{y}\end{pmatrix}}{\begin{pmatrix}u_{x}\\u_{y}\\v_{x}\\v_{y}\\u_{z}\\v_{z}\end{pmatrix}}={\begin{pmatrix}B_{x}\\B_{y}\\C_{x}\\C_{y}\\D_{x}\\D_{y}\end{pmatrix}}$

And some simple row operations

${\begin{pmatrix}1&0&0&0&-B_{x}&0\\0&1&0&0&-B_{y}&0\\0&0&1&0&0&-C_{x}\\0&0&0&1&0&-C_{y}\\0&0&0&0&B_{x}-D_{x}&C_{x}-D_{x}\\0&0&0&0&B_{y}-D_{y}&C_{y}-D_{y}\end{pmatrix}}{\begin{pmatrix}u_{x}\\u_{y}\\v_{x}\\v_{y}\\u_{z}\\v_{z}\end{pmatrix}}={\begin{pmatrix}B_{x}\\B_{y}\\C_{x}\\C_{y}\\D_{x}-B_{x}-C_{x}\\D_{y}-B_{y}-C_{y}\end{pmatrix}}$

Taking the bottom right 2 by 2 partition

${\begin{pmatrix}B_{x}-D_{x}&C_{x}-D_{x}\\B_{y}-D_{y}&C_{y}-D_{y}\end{pmatrix}}{\begin{pmatrix}u_{z}\\v_{z}\end{pmatrix}}={\begin{pmatrix}D_{x}-B_{x}-C_{x}\\D_{y}-B_{y}-C_{y}\end{pmatrix}}$

This smaller matrix is singular when the vectors ${\vec {B}}-{\vec {D}}$ and ${\vec {C}}-{\vec {D}}$ are co-linear, this is the degenerate case when the target quadrilateral is a line. Solving this smaller matrix gives the z-coordinates $u_{z},\ v_{z}$ and the rest is easy once they are known.--Salix (talk): 23:34, 27 March 2013 (UTC)

• Let me add a note that it's not too hard to find code that solves this problem. For example in GIMP the Perspective Tool allows the user to specify a perspective transformation by moving the corners of a square -- it then calculates the necessary transformation matrix and applies it to the image. The code for this is in C -- you can find other versions that solve the same problem in Java and other languages if you look around. Looie496 (talk) 16:19, 27 March 2013 (UTC)

That again does the inverse of what I'm interested in. I have the texture coordinates and want the screen coordinates. Problem solved though (see above). Eonzo (talk) 19:59, 27 March 2013 (UTC)

• But are you sure it isn't just doing it linearly ? StuRat (talk) 16:22, 27 March 2013 (UTC)

I'll mark this Q resolved for you. Would you mind posting your finished code and/or the coords for each point in that final grid, above ? I'd like to implement it myself. StuRat (talk) 20:18, 27 March 2013 (UTC)

Will do so tonight. I wrote the test app in Delphi but quite simple to convert to C or something. 105.236.159.11 (talk) 05:46, 28 March 2013 (UTC) Eon

OK, thanks, it will be much appreciated. I'm taking a class in 3D computer graphics now. StuRat (talk) 07:03, 28 March 2013 (UTC)

Program source code.

// Reference points on a 512 x 512 canvas (Y increases downward): const POINTS: array[0..3] of TVector2D // TVector2D is a simple vector type with X and Y = ((X: 256 - 160; Y: 256 + 160), // A; (U, V) = (0, 0) (X: 256 + 200; Y: 256 + 200), // B; (U, V) = (0, 1) (X: 256 - 200; Y: 256 - 200), // C; (U, V) = (1, 0) (X: 256 + 80; Y: 256 - 80)); // D; (U, V) = (1, 1) // Variables (excludes drawing API objects): var i, j : Integer; U, V, X, Y : Single; AMatrix : array[0..35] of Single; // 6 x 6 matrix in Ax = b bVector : array[0..5] of Single; // 6 x 1 matrix/vector in in Ax = b // Code: // Draw black reference points Brush.SetColor(MakeColor(0, 0, 0)); // Black for i := 0 to 3 do Graphics.FillEllipse(Brush, POINTS[i].X - 5, POINTS[i].Y - 5, 10, 10); // Draw the four black dots (with a diameter of 10) // Note: AMatrix elements are arranged as follows: // 0, 1, 2, 3, 4, 5; // 6, 7, 8, 9, 10, 11; // 12, 13, 14, 15, 16, 17; // 18, 19, 20, 21, 22, 23; // 24, 25, 26, 27, 28, 29; // 30, 31, 32, 33, 34, 35; // Initialize matrix with all zeros for i := 0 to 5 do for j := 0 to 5 do AMatrix[6 * i + j] := 0; // Fill in nonzero elements in A matrix (note that both my AMatrix and bVector is negated compared to Salix's) AMatrix[0] := -1; AMatrix[7] := -1; AMatrix[15] := -1; AMatrix[22] := -1; AMatrix[24] := -1; AMatrix[27] := -1; AMatrix[31] := -1; AMatrix[34] := -1; AMatrix[2] := (POINTS[1].X - POINTS[0].X); // Note we subtract A (POINTS[0]), to make it so that A was effectively (0, 0) AMatrix[8] := (POINTS[1].Y - POINTS[0].Y); AMatrix[17] := (POINTS[2].X - POINTS[0].X); AMatrix[23] := (POINTS[2].Y - POINTS[0].Y); AMatrix[26] := (POINTS[3].X - POINTS[0].X); AMatrix[32] := (POINTS[3].Y - POINTS[0].Y); AMatrix[29] := (POINTS[3].X - POINTS[0].X); AMatrix[35] := (POINTS[3].Y - POINTS[0].Y); // Fill in b vector bVector[0] := -(POINTS[1].X - POINTS[0].X); bVector[1] := -(POINTS[1].Y - POINTS[0].Y); bVector[2] := -(POINTS[2].X - POINTS[0].X); bVector[3] := -(POINTS[2].Y - POINTS[0].Y); bVector[4] := -(POINTS[3].X - POINTS[0].X); bVector[5] := -(POINTS[3].Y - POINTS[0].Y); // SolveMatrix does Gauss-Jordan elimination, replacing the b vector with the solution x as in Ax = b // This is similar to the function in Numerical Recipes in C, but doesn't require special structure definitions if not SolveMatrix(@AMatrix[0], 6, @bVector[0], 1) then begin ShowMessage('Could not solve :('); // Pops up error message Exit; end; // bVector is now [u_x, u_y, u_z, v_x, v_y, v_z]' // Plot the green interpolated points on a 10 x 10 grid of intervals (11 x 11 grid of points) Brush.SetColor(MakeColor(0, 160, 0)); // Green for i := 0 to 10 do begin V := i / 10; // Note that in Delphi "/" always means floating point division for j := 0 to 10 do begin if (j mod 10 = 0) and (i mod 10 = 0) then Continue; // We don't draw over the original four black dots U := j / 10; X := Points[0].X + (U * bVector[0] + V * bVector[3]) / (1 + U * bVector[2] + v * bVector[5]); Y := Points[0].Y + (U * bVector[1] + V * bVector[4]) / (1 + U * bVector[2] + v * bVector[5]); Graphics.FillEllipse(Brush, X - 5, Y - 5, 10, 10); // Draw the green dots end; end;

Above is the mathematics part of the source code that generated the image with the 117 green dots. It relies on a "SolveMatrix" procedure - for something similar, look for LinearEquations.c here. I pack the 6 x 6 matrix into a 36 element array, which is how my SolveMatrix wants it. 41.164.7.242 (talk) 14:52, 28 March 2013 (UTC) Eon

Here's a link directly to LinearEquations.c (yours is a page containing the link to it): [2]. StuRat (talk) 16:29, 28 March 2013 (UTC)

Sample point data.

96.000, 416.000 194.182, 426.909 276.000, 436.000 345.231, 443.692 404.571, 450.286 456.000, 456.000 85.091, 317.818 176.000, 336.000 252.923, 351.385 318.857, 364.571 376.000, 376.000 426.000, 386.000 76.000, 236.000 160.615, 259.077 233.143, 278.857 296.000, 296.000 351.000, 311.000 399.529, 324.235 68.308, 166.769 147.429, 193.143 216.000, 216.000 276.000, 236.000 328.941, 253.647 376.000, 269.333 61.714, 107.429 136.000, 136.000 201.000, 161.000 258.353, 183.059 309.333, 202.667 354.947, 220.211 56.000, 56.000 126.000, 86.000 187.765, 112.471 242.667, 136.000 291.789, 157.053 336.000, 176.000

Sorry for taking up so much space on this page. Above is a 5 x 5 grid of intervals (6 x 6 grid of points). 41.164.7.242 (talk) 15:11, 28 March 2013 (UTC) Eon

I collapsed them for you. Thanks for posting it. If someone has a similar question in the future, we can refer them here. StuRat (talk) 16:24, 28 March 2013 (UTC)

Resolved

Why Are All Basic Irrationals So Close to Multiples of 1/7 ?

$\pi \approx {22 \over 7}=3{1 \over 7}\ \ \ \ \ \ \ \ \ \ e\approx {19 \over 7}=2{5 \over 7}\ \ \ \ \ \ \ \ \ \ \gamma \approx {4 \over 7}$

${\sqrt {2}}\approx {10 \over 7}=1{3 \over 7}\ \ \ \ \ \ \ \ \ \ {\sqrt {3}}\approx {12 \over 7}=1{5 \over 7}\ \ \ \ \ \ \ .$ 79.113.221.135 (talk) 15:16, 26 March 2013 (UTC)

Interesting observation, but there can't really be any reason for this. Mathematics just is what it is. There are "reasons why" when you get into theorems, but not general observations. IBE (talk) 15:55, 26 March 2013 (UTC)

You sure `bout that ? :-) — 79.113.209.59 (talk) 02:45, 27 March 2013 (UTC)

Well, technically no. But I doubt there is much to a general observation of this sort, though I'm going through the interesting replies below. IBE (talk) 08:00, 27 March 2013 (UTC)

Let's list the deviation of each:

$\pi \approx {22 \over 7}=3{1 \over 7}$ Deviation = 0.040%

$e\approx {19 \over 7}=2{5 \over 7}$ Deviation = 0.147%

$\gamma \approx {4 \over 7}$ Deviation = ?

${\sqrt {2}}\approx {10 \over 7}=1{3 \over 7}$ Deviation = 1.015%

${\sqrt {3}}\approx {12 \over 7}=1{5 \over 7}$ Deviation = 1.026%

The last two aren't particularly close. I'm not sure what you had in mind for the value of gamma. For the square root of 2, you'd do a lot better with 99/70, which has a deviation of only 0.005%. For the square root of 3, 97/56 also gives a deviation of only 0.005%. StuRat (talk) 16:13, 26 March 2013 (UTC)

70 and 56 are significantly larger numbers than the 'humble' 7. So it is obviously to be expected that if the resolution or precision is so great, the approximation will also be significantly better. But in the case of the small number 7, this is not something that one might exactly `expect`. Yet, nevertheless, it happens. Why ? (Furthermore, both 70 and 56 are multiples of 7). — 79.113.221.135 (talk) 19:13, 26 March 2013 (UTC)

My point is, with a denominator only 8 or 10 times bigger, we can get a deviation less than 1/200th as large. StuRat (talk) 17:46, 27 March 2013 (UTC)

I suppose that'd be the Euler-Mascheroni constant, which has a deviation from $4 \over 7$ of around 1.00%. 129.234.186.45 (talk) 17:28, 26 March 2013 (UTC)

OK, thanks. StuRat (talk) 18:45, 26 March 2013 (UTC)

The reason is that you can express many of them as the sums of a rapidly convergent series expansions. The denomerator of the nth term will typically only have factors that divide n (or some fixed multiple of n). Typically, you have to go quite far in the series expansion before you encounter a term that has 11 in the denominator. So, a quite accurate approximation will be obtained by adding up terms that in the denominator contain prime numbers up to 7. Adding up such terms will, of course, not yield new prime numbers that are not present in the denominators of the terms that are added up. What can happen is that upon summation, a factor gets canceled out. So, there will be cases where you get a very good approximation by including a term containing 11 in the denominator, but when added up to the other terms, that 11 gets canceled out and you are left with only factors up to 7 in the denominator. Count Iblis (talk) 17:40, 26 March 2013 (UTC)

Could you be a bit more explicit about what kind of rapidly-convergent series you had in mind ? Thanks. — 79.113.221.135 (talk) 19:16, 26 March 2013 (UTC)

Taylor series are the classic ones. For example, you can come up with an approximation for pi by evaluating the expansion for arcsin at x=0. Depending on what value you're evaluating, there may be other types of series approximations which apply. -- 205.175.124.30 (talk) 21:26, 26 March 2013 (UTC)

Hmmm, my argument only shows that fractions with denominators that have prime numbers up to 7 will yeiled good approximations, but then you can have factors of 2,3, and 5 in there as well. So, one would have to argue that you have so much choice between different approximations that all have only those factors in the denominator that there will likely be one that is free of factors of 2, 3 and 5. Count Iblis (talk) 23:37, 27 March 2013 (UTC)

Two of your examples are algebraic numbers, two are transcendental numbers, and one is unknown. In fact, the irrationality of \gamma is unknown (according to the second link). For the approximation of transcendentals by rationals, check out Transcendence_theory#Approximation_by_rational_numbers:_Liouville_to_Roth and links therein. See also this nice book chapter on rational approximation [3]. SemanticMantis (talk) 21:26, 26 March 2013 (UTC)

I also encourage you to question your premises. You claim "all basic irrationals" have a property of being "close" to multiples of 1/7. What is a "basic" irrational? What is "close?" But more importantly, you have shown four examples. Have a look at Texas_sharpshooter_fallacy. SemanticMantis (talk) 21:30, 26 March 2013 (UTC)

$\pi ,e,$ and ${\sqrt {2}}$. (I could've also easily added $e^{\pi }$ and $e \over \pi$ to the list, but I chose to keep it simple). — 79.113.209.59 (talk) 02:36, 27 March 2013 (UTC)

OTOH ${\sqrt {7}}$ and ${\sqrt {1}}9$ are each close to an odd multiple of 1/14, so almost as far away from a multiple of 1/7 as you can get. Gandalf61 (talk) 09:29, 27 March 2013 (UTC)

If only 14 would not have been a multiple of 7, or if multiples of either 1/13 or 1/15 would've made for better approximations... [P.S.: Just to be clear: I wasn't suggesting that ALL irrationals are best approximated by multiples of 1/7, or anything like that... I was only curious as to why these famous ones are, that's all]. The only other famous or noteworthy irrational to which this observation does not apply is the golden ratio, probably because ${\sqrt {5}}$ is best approximated by $2{1 \over 4}$. — 79.113.233.238 (talk) 14:21, 27 March 2013 (UTC)

• Because the only primes lower than the base in base ten are 2,3,5 and 7, and 2 and 5 factor evenly into 10, while 3 factors into 10 with an immediate repetition (3.333) while 7 does not. If we used a different base this would not then be the case. μηδείς (talk) 21:36, 26 March 2013 (UTC)

By `different` I assume you mean `larger`, otherwise the statement is incorrect. — 79.113.209.59 (talk) 02:36, 27 March 2013 (UTC)

I don't think the base makes any difference whatsoever. Things like primeness and divisibility don't change, although the representation of the numbers does. I don't think the OP's question has anything to do with representations of numbers, so 7 in base 2 is still 7. IBE (talk) 08:05, 27 March 2013 (UTC)

Well, in that case, an error of under 1% is still an error of under 1% in base 2 as well, so... — 79.113.233.238 (talk) 14:16, 27 March 2013 (UTC)

Approximations of irrationals using fractions over seven are convenient in base ten because they yield a long repeating string 1/7 = 0.142857142857 2/7 = 0.285714285714, etc., whereas using fractions over the other digits either terminate quickly 1/4 = 0.25 or repeat in only one digit as when dividing by 3, 6, or 9. This long repeating terminator with irreducible fractions over seven always show the same six numbers in the same sequence 285714285714285714; but which of those nubers begins the sequence depends on the remainder.

A fraction with a remainder of two will always come out N.285714285714, a fraction with a remainder of one will always come out N.142857142857, and so on. This means by selecting what remainder we have we can select which of those six number will begin the sequence, allowing us the options of representing any numbers of the form X + 0.14..., X + 0.28..., X + 0.42..., X + 0.57..., X + 0.71..., or X + 0.85 (As well as X + 0.00 when there's no remainder). So, if we want to represent Pi, we separate the 3 from the .1415926, multiply the 3 times seven, and add the remainder which gives the closest of those six options: in this case 1, giving (21+1)/7 as our approximation.

For e, 2.718281828... base of the natural logarithm, we chose a remainder of five (X + 0.71...) as closest to the value of the digits after the decimal, then add that remainder of five to seven times the number before the decimal, in this case 2, to get our approximation: e ~ ((2x7)+5)/7 or 19/7, which equals 2.71428571 for am error of about 0.4%.

The worst case scenario is going to be an irrational whose decimal remainder is something like .213456, which will lie half way between our options of .142857 and .285714--in which case we can change from fractions over 7 to more suitable higher prime denominators such as 17 with its 16 repeating decimals: 1 / 17 = 0.0588235294117647 and its 16 more precise .05, .11, .17, .23, .29, etc.)optional remainders.

In other bases, like base 14, the choice of prime denominators for this procedure will obviously vary since they will either terminate or repeat with a different length remainder. But the process is simple and the reason why we use 7 for this in base 10 is obvious. μηδείς (talk) 17:36, 27 March 2013 (UTC)

I don't see how the base makes any difference at all. The magnitude of the difference between, say, e and the nearest multiple of 1/7 is the same no matter what base you work in. Gandalf61 (talk) 19:56, 27 March 2013 (UTC)

The question is, why does the small prime 7 serve so well to express irrational numbers. The base doesn't matter for the ratio between the denominator and the irrational constant. What matters for the convenience of expression is the number of repeating decimals after the decimal point, which will vary with different primes differently under different bases.

According to our article there is no way to predict how many repeating decimals will come after the decimal point for a given prime in a different base. For example, as shown above, 7 and 17 have p-1 (i.e., 6 and 16) repeating decimals, while 13 has only 6, not 12. These numbers that have p-1 repeating numbers are called cyclic numbers

Not all primes are cyclic in each base, many have fewer than p-1 in a certain base. While 1/29 (= 0.0344827 5862068 9655172 4137931) has 28 repeating digits an hence can approximate 28 remainders: .03, .06. .10, .13, .17, .20... etc., the prime 41 has only five repeating digits: 0.0243902439, and these do not "rotate" like those of 7 or 17 allowing easy approximational expressions.

Of course one can get great hard-to-remember approximations of Pi and other irrationals using brute force and huge denominators: 2862 / 911 = 3.14160263 But if you want to use a small prime to do this only certain options are good ones. μηδείς (talk) 20:47, 27 March 2013 (UTC)

Medeis, I'm araid I have to agree with Gandalf here, despite not being a huge fan of Lord of the Rings... :-) Sorry. — 79.113.233.238 (talk) 23:11, 27 March 2013 (UTC)

Well, I am not exactly sure what it is you agree on with Gandalf, but it's your question, there's no requirement you accept a rational answer to it. μηδείς (talk) 03:39, 28 March 2013 (UTC)

Numeration bases are like languages... it doesn't matter whether you say love or amore, the two words have the same meaning. Likewise, numbers have the same value (and their approximations have the same precision), regardless of what numeration system one might choose to use to express them in. — 79.113.233.238 (talk) 03:53, 28 March 2013 (UTC)

Correct. The best rational approximations to an irrational number can be derived from its continued fraction expansion, which is base independent. Medeis - if you disagree, perhaps you can explain exactly how you think that 22/7 becomes a better or more natural approximation to π when expressed in decimal than when expressed in, say, binary or octal ? Gandalf61 (talk) 09:30, 28 March 2013 (UTC)

Unresolved

Independence number of a cycle

Is it true that the independence number of a cycle is $\lfloor n/2\rfloor$? It is easy to see that if the cycle is given by $v_{1}v_{2}\cdots v_{2m+1}$ then $\{v_{1},v_{3},\cdots ,v_{2m-1}\}$ form an independent set having $\lfloor n/2\rfloor$ elements in the case of an odd cycle and the alternate vertices form an independent set in the case of an even cycle. But where can I find a proof that this is the independent set of maximum cardinality? Thanks.--Shahab (talk) 17:10, 26 March 2013 (UTC)

Every vertex is an endpoint of two edges of the cycle, and no two vertices in an independent set can be endpoints of the same edge. So every vertex of the independent set "uses up" two edges of the graph. The graph has only n edges in all. —Bkell (talk) 18:03, 26 March 2013 (UTC)