Mathematics desk
< November 17	<< Oct \| November \| Dec >>	November 19 >

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.

November 18

Bring radical and an Extended Abel–Ruffini theorem

Given a polynomial P with P(0) = 0, define a P-radical to be a map f of the base field into itself so that for all a, f(a) is a root of P(X) - a. Is there anything like the Abel-Ruffini theorem, or any Galois Theory stuff, that is applicable to the question of what polynomials can be solved using P-radicals for P belonging to a given set of polynomials? More specifically, this question is inspired by adding things like the, above mentioned, Bring Radical to the bag of tricks involved in solving higher degree polynomial equations. For the purposes of this specific question, I'm considering adding something like the current radical, I know that there are analytic flavoured things that can do the job, and would be interested to an algebraic analysis of their power, if it exists, but I am mainly interested in reflecting what we are able to use to solve the equation in properties of algebraic structures associated to it (as the case with galois groups). Thank you for any insight or leads on this matter:-)Phoenixia1177 (talk) 08:26, 18 November 2014 (UTC)[reply]

Radian increment to cover a square grid

I am going through old programming problems to include in an upcoming programming competition. This is one that I solved, but my solution was brute force. Is there an elegant mathematical solution...

A pixel-based system needs to check that every pixel in a circle is shaded. It begins with a center (xc, yc) and a radius, r (radians). The first point to check is (xc, yc+r). It will then increment r by i until r = 2*PI (a full circle). For reference, if x is initially xc and y is initially yc+r, r will become r+i and the new (x, y) will be (xc+(x-xc)*cos(r)-(y-yc)*sin(r), yc+(x-xc*sin(r)+(y-yc)*cos(r)). What is the maximum increment (i) that may be used to ensure that every pixel on the circle is checked? It is assumed that i will be dependent on r. A smaller increment will be required for larger values of r.

My solution tried an increment of 0.001 and incremented it by 0.001 until one of the pixels was skipped. It was quick and dirty to program, but definitely not elegant. 209.149.113.112 (talk) 15:45, 18 November 2014 (UTC)[reply]

I am confused by your statement of the problem. You wrote that it begins with a "radius, r (radians)". A radius is typically not measured in radians. Your later "(xc, yc+r)" uses r as a radius, but "increment r by i until r = 2*PI" us r as an angle. Did the original statement include separate R (radius) and r (angle)? -- ToE 21:43, 19 November 2014 (UTC)[reply]

Having written programs to do that exact same thing, I can tell you it's more efficient to scan a square and check if each point is within the circle:

RADIUS_SQUARED = RADIUS^2
DO X = Xc-RADIUS TO Xc+RADIUS
  DO Y = Yc-RADIUS TO Yc+RADIUS
    IF (Xc-X)^2 + (Yc-Y)^2 <= RADIUS_SQUARED
      (SHADE IT)
    ENDIF
  ENDDO
ENDDO

If you insist on using polar coords, you would want to change the rotation increment at each radius step to make it efficient, and you will have to worry about round-off error when converting real numbers to integers, etc. And even if you get this all right, the overhead of constantly converting from polar coords to rectangular coords will still make this approach slower. StuRat (talk) 22:35, 19 November 2014 (UTC)[reply]

I am unsure if the original question is really about shading the disc inside a circle or about drawing the circumference. "to check that every pixel in a circle is shaded" sounds like the former, but the algorithm alluded to sounds like the latter (although the next step might be drawing a line from the center to the moving point on the circumference). Perhaps the questioner can point us to the text of the original problem. -- ToE 00:04, 20 November 2014 (UTC)[reply]

Question re-asked down below at #Minimum angle between edges of a circle in a grid. -- ToE 21:47, 20 November 2014 (UTC)[reply]

2-D random walk (all turns) back to start?

Set a 2D random walk with all steps of length 1 with the following additional conditions. The first step is from (0,0) to (1,0), after every step, the next step must be at right angles to the last (so after (1,0) the next step must be to (1,1) or (1,-1)). For this walk, what is the chance that the first time that the walk goes back to a previous point that it is going back to 0,0 (forming a loop) and of *that* chance what is the probability that it will form a *proper* loop (coming back to 0,0 from either 0,1 or 0,-1)Naraht (talk) 15:59, 18 November 2014 (UTC)[reply]

Here's a nice chapter on properties of Euclidean random walks [1]. I suspect you can answer some of your questions by following their steps, while substituting in your rules. Of course the results of e.g. first return time will be different, but the methods should be similar and possibly easier. SemanticMantis (talk) 16:12, 18 November 2014 (UTC)[reply]

Unless I'm reading this wrong, this is a Minkowski random walk. 209.149.113.112 (talk) 16:23, 18 November 2014 (UTC)[reply]

First of all, if you are required to make right/left turns, Minkowski space becomes striped. You state that from 1,0 the move must be up/down (moving along y). Every odd value of x is up/down. Every even value of x is right/left. Therefore, it is impossible to move from 1,0 to 0,0 because x is odd and the only moves allowed are along the y axis (same applies for -1,0). That means that for every loop, it is a proper loop. Now, how many loops are there? I prefer to just simulate. There will be a loop (proper loop) 27% of the time based on 1,000,000,000 random walks. With an approximate answer, you can work on a proof that gets close to that answer. The proof will be an exact answer, not an approximate one like mine. 209.149.113.112 (talk) 16:43, 18 November 2014 (UTC)[reply]

Yeah, I'd figured out after I posted it that all loops had to be proper loops, with somewhat similar logic to yours. And 1/8 of the random walks will start out LLL and 1/8 will start out RRR which gives you 25% being the simple square loops and I'm actually surprised that the ones that aren't that represent 2%. These would be ones that not only go back to 0,0 but that don't go back to the same point prior to that, so the smallest non square is the outline of a 5 square cross.Naraht (talk) 15:16, 19 November 2014 (UTC)[reply]

Why have I never been included in a "random survey"?

For the purposes of this question I'll work with "round numbers".

I live in South Africa - current population 50 million - when I became an adult 30 years ago and thus eligible to be "randomly surveyed" the population was 35 million (assume a constant population growth rate). According to the Bachelors level course in social research I took this year, about 1000 "random surveys" of about 1000 people take place every year in this country - for everything from new toothpaste varieties to political opinions. So what are the odds that out of 30 000 surveys over 30 years not a single one has ever picked me? Does it say anything about the randomness of the surveys, or my ability to consistently dodge people with clipboards? Roger (Dodger67) (talk) 18:10, 18 November 2014 (UTC)[reply]

One thing to consider is that scientific surveys (e.g. for academic research in social sciences) are carefully designed to be very uniformly random, to avoid response bias. On the other hand, product surveys are not fully randomized, and they may pay attention to "likely shoppers" or other such sub groups. These groups tend to have a lot of overlap, and if you ever do one such product survey, you will be asked to do many more (because you have a better chance of not ignoring the request and hence wasting their efforts). Adding to the confusion is that many scientific surveys should be random, but they tend to biased towards college students, in part because some of them have to participate in studies to get full class credits. [2]. So, among the 1k surveys each year, most of them are probably not properly randomized, and that will negatively influence your chances of being selected. See Total_survey_error for more info.

Finally, to compute the probability of NOT being chosen in 30 years, assuming that every study in SA is fully uniformly random, work it out as the product of the probabilities of not being chosen each year.

E.g.

\prod _{n=1}^{30}\left(1-{\frac {1000*1000}{P_{n}}}\right)

, where P_n is the population in year n, with n=1 being 2014-30. Since it is a very rough model anyway (due to the assumption of real independent, uniform selection), you can shortcut and just look at

\left(1-{\frac {1000*1000}{P}}\right)^{30}

, where P is some fixed population. Doing that for P=40m gives me ~47% chance of NOT getting chosen, though the actual probability will likely be notably higher, for the reasons I've mentioned. Make sense? SemanticMantis (talk) 19:36, 18 November 2014 (UTC)[reply]

P.S. You also may have been "selected" and not even noticed. Product surveys often look like any other junk mail in the USA, and I bet I've recycled a few without even noticing. SemanticMantis (talk) 19:41, 18 November 2014 (UTC)[reply]

Do you have a "land line" phone ? Here in the US almost all surveys seem to be done that way. So, if it's the same in SA, and you only have a mobile phone, that might explains things. StuRat (talk) 04:14, 19 November 2014 (UTC)[reply]