Wikipedia:Reference desk/Mathematics

Welcome to the mathematics section
of the Wikipedia reference desk.

skip to bottom

Select a section:

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

Want a faster answer?

Main page: Help searching Wikipedia

   

How can I get my question answered?

• Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
• Post your question to only one section, providing a short header that gives the topic of your question.
• Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
• Don't post personal contact information – it will be removed. Any answers will be provided here.
• Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
• Note:
  • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
  • We don't answer requests for opinions, predictions or debate.
  • We don't do your homework for you, though we'll help you past the stuck point.
  • We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

Ready? Ask a new question!

How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

• The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.

See also:

• Teahouse
• Help desk
• Village pump
• Help manual

December 3

Natural logarithm

Why is the natural logarithm ln rather than nl or something else? --70.250.212.95 (talk) 00:47, 3 December 2011 (UTC)

Our article on it says that it was once called "logarithmus naturalis", which sounds like Latin.--121.74.125.249 (talk) 01:05, 3 December 2011 (UTC)

...which illustrates that English is only one of the (obviously many) languages in which mathematics is expressed, and many of them place adjectives after the nouns they modify. In any event, there is a strong, broad convention throughout mathematics and science to build notation that way—from the outside in, if you will. Two examples:

-If a statistician wished to invent variables to represent the respective probabilities that a tossed coin might result in heads and tails, he'd likely use P_H and P_T rather than, say H_P and T_P.

-When mathematicians wish to index a set of variables sequentially, they write things like x₁ and x₂, rather than ₁x and ₂x.

—PaulTanenbaum (talk) 17:55, 3 December 2011 (UTC)

Integrability

hello. today in the calculus class that I AP (along with one other grad student) we introduced Riemann integration and the other said something to the effect that for a function to be integrable, it must not have "too many holes" (informally speaking), that is it must only be discontinuous on a finite number of points. I countered from my memory of real analysis (which may be faulty, I do stats, not a mathematician proper :S) a theorem that as long as the function's discontinuities are countable set of points, even if they are infinite, the funcion is integrable. But then I thought about the Dirichlet function, which is defined (one of many ways) as f(x)=x for rational x, 0 for irrational x. Since the rationals are countable the function should be integrable if the theorem I recalled is valid but the DIrichlet function is clearly not Riemann integrable (it is Lebesgue integrable, but that is something else altogether). I think I am misstating the theorem- I knew it had something to do with countability, can anyone help me out? THanks. 24.92.85.35 (talk) 01:21, 3 December 2011 (UTC)

A function is Riemann integrable if and only if the set of discontinuities has Lebesgue measure zero. Measure zero sets include finite sets, countable sets, and even some uncountable sets (like the cantor set). The set of all irrational numbers in [0,1] has lebesgue measure one. The dirichlet function is discontinuous on all the irrational numbers and therefore NOT Riemann integrable. For the longest time everyone worked hard on this to figure what exactly are the necessary and sufficient conditions on a function to be integrable. Riemann came along and fixed up the integral (meaning defined it properly) and put it upon solid ground and proved many of its properties from this new definition, which everyone had previously taken for granted since Newton. He made the question well posed and hence the integral is named in his honor. And then Henri Lebesgue was the first one who successfully answered this question and also generalized the Riemann integral.71.211.145.44 (talk) 03:02, 3 December 2011 (UTC)

To be precise, a function on an interval [a,b] is Riemann integrable if and only if it is bounded and the set of discontinuities has Lebesgue measure zero. 78.13.145.217 (talk) 22:54, 6 December 2011 (UTC)

December 4

Question about eigenvectors and eigenvalues

Hi Reference Desk, I have 2 questions about eigenvectors and eigenvalues in the context on Singular Value Decomposition.

In my linear algebra textbook (undergraduate), it says that |Ax| = |λx| = |λ| |x| = |λ|. I understand how it goes from |Ax| to |λ| |x|, but I don't understand how it went from |λ| |x| to just |λ|.

Also, in an example where a matrix A is described to linearly transform a unit sphere {x: |x| = 1} in R^3 onto an ellipse in R^2, we were told to find a unit vector at which the length |Ax| is maximized and compute this maximum length. The solution says that the quantity |Ax|^2 is maximized at the same x that maximizes |Ax| (which I understand), but it also says that |Ax|^2 = (Ax)^T(Ax) = x^T A^T A x = x^T (A^T A) x. Why is it that |Ax|^2 = (Ax)^T (Ax) ?

Thanks — Preceding unsigned comment added by 169.232.119.135 (talk) 06:57, 4 December 2011 (UTC)

For the first one, presumably x is a unit vector. I think the context is needed.

For the second one, it's a well known identity that $|x|^{2}=x^{T}x$ for any vector x. $|x|$ is by definition ${\sqrt {x\cdot x}}$ and it should be pretty obvious that $x\cdot x=x^{T}x$. If you choose some arbitrary x and you try to calculate $x\cdot x$ and $x^{T}x$ you will find that you really use literally the same procedure for evaluating both of them. Widener (talk) 07:08, 4 December 2011 (UTC)

Thanks Widner, I now understand those 2 problems. The context for the first question was indeed where x is a unit vector. — Preceding unsigned comment added by 169.232.72.232 (talk) 19:07, 4 December 2011 (UTC)

Algebra Problem

Find all pairs of real numbers (x,y) such that 16^x2+y+ 16^x+y2=1 117.227.104.36 (talk) 14:07, 4 December 2011 (UTC)

Is this homework? If so, we can only give hints. Turn the LHS into a function, find its absolute minima, etc. It comes out neatly (I think). We'll help more if you convince us it isn't homework, and ask nicely, etc. IBE (talk) 15:49, 4 December 2011 (UTC)

Hint, the answer(s) are in neat format. And note that any values of x and y where either is 1 or larger in absolute value will give a value that is too large.Naraht (talk) 16:16, 4 December 2011 (UTC)

$\left(-{\frac {1}{2}},-{\frac {1}{2}}\right)$ Widener (talk) 01:08, 5 December 2011 (UTC)

Closed form series solution

Please help me evaluate

• $\sum _{n=0}^{\infty }{\frac {1}{(n+{\tfrac {1}{2}})(n-{\tfrac {1}{2}})}}x^{n}=-{\frac {1}{4}}{}_{2}F_{1}(-{\tfrac {1}{2}},0;{\tfrac {3}{2}};x)$

in closed form, near x = 0. My copy of Abramowitz and Stegun is in softcopy image, and is difficult to search, and 0 as an upper index is problematic. — Arthur Rubin (talk) 19:06, 4 December 2011 (UTC)

Just an fyi, Abramowitz and Stegun is available legally online, including in searchable pdf form. Otherwise, check Hypergeometric function on wiki or Mathworld. I won't help with the problem as that's typically a recipe for stealing my study time for the next two hours. SamuelRiv (talk) 23:44, 4 December 2011 (UTC)

I'm getting

$-{\frac {1}{4}}{}_{2}F_{1}(-{\tfrac {1}{2}},0;{\tfrac {3}{2}};x)=-{\frac {1}{4}}$

$\sum _{n=0}^{\infty }{\frac {1}{(n+{\tfrac {1}{2}})(n-{\tfrac {1}{2}})}}x^{n}={\frac {2(x\tanh ^{-1}({\sqrt {x}})-\tanh ^{-1}({\sqrt {x}})-{\sqrt {x}})}{\sqrt {x}}}=-4+{\frac {4x}{3}}+{\frac {4x^{2}}{15}}+O(x^{3})$

-- Meni Rosenfeld (talk) 09:45, 5 December 2011 (UTC)

That should have been

• $\sum _{n=0}^{\infty }{\frac {1}{(n+{\tfrac {1}{2}})(n-{\tfrac {1}{2}})}}x^{n}=-\mathbf {4} {}_{2}F_{1}(-{\tfrac {1}{2}},\mathbf {1} ;{\tfrac {3}{2}};x)$

and that 1 as an upper index is problematic. I shouldn't post while asleep.

Rewriting your expression, I get

$\sum _{n=0}^{\infty }{\frac {1}{(n+{\tfrac {1}{2}})(n-{\tfrac {1}{2}})}}x^{n}={\frac {2(x\tanh ^{-1}({\sqrt {x}})-\tanh ^{-1}({\sqrt {x}})-{\sqrt {x}})}{\sqrt {x}}}=-2-2(1-x){\frac {\tanh ^{-1}{\sqrt {x}}}{\sqrt {x}}}$

which is exactly what I was looking for, as it also explains why it remains a power series at 0. — Arthur Rubin (talk) 15:33, 5 December 2011 (UTC)

Find point closest to a plane

Hi all,

I am wondering how I can use linear algebra to tackle this problem which was on my midterm:

"Let P denote the plane passing through the points (5, 2, 1), (7, 2, 3), (5, 5, 1). Notice that this plane does not pass through the origin. Find the point on P that is nearest to (10, 10, 10)"

I tried using the least squares solution, i.e. x* = (A^T A)^-1 A^T b where A is the matrix formed by the 3 points that the plane passes through (in columns), and b is (10, 10, 10). Since I ran out of time on the midterm, I only went as far as calculating (A^T A) is. However, the grader crossed out my work completely. Am I at least on the right track? I tried using my GDC at home to calculate this and the answer I got is (-25/3, 5, 10/3).

Is it possible to use other methods to solve this problem other than the least square solution? I thought about Lagrange multipliers, but I'm not sure what my F and G should be. I suppose the function that I want to optimize will be the distance formula d^2 = (x-10)^2 + (y-10)^2 + (z-10)^2 and the constraint would be the equation of the plane (which I have yet to calculate). — Preceding unsigned comment added by 169.232.72.232 (talk) 20:45, 4 December 2011 (UTC)

The point on P closest to (10,10,10) is the point, say p, such that the chord joining p to (10,10,10) is perpendicular to P. The equation of P is x – z = 4. The vector (1,0,–1) is perpendicular to P. For the point on P, closest to (10,10,10), we need to set off from (10,10,10) in the direction (1,0,–1) and see which point we meet P. Consider

$q(\lambda ):=(10,10,10)+\lambda (1,0,-1)=(10+\lambda ,10,10-\lambda )\,.$

The point q(λ) lies on the plane P when x – z = 4, i.e. when

$(10+\lambda )-(10-\lambda )=4\,\implies \lambda =2\,.$

Since q(2) = (12,10,8), I make (12,10,8) the point on P which is closest to (10,10,10). — Fly by Night (talk) 21:33, 4 December 2011 (UTC)

What you were trying to do with the least squares would give you the closest point to P in the 3-dimensional space which includes 0 and is spanned by the 3 vectors. This space is $\mathbb {R} ^{3}$ since the vectors are linearly independent, so what you would get is P itself (and what you denoted by x* is just the coordinates, to get the actual point you need to multiply by A). To use least squares you can translate everything so that the plane does go through the origin, for example by moving (5,2,1) to (0,0,0). Then you get the plane spanned by (2,0,2) and (0,3,0), and the point (5,8,9). Don't forget to translate the result back. -- Meni Rosenfeld (talk) 18:43, 5 December 2011 (UTC)

Searching for patters in a lattice

I've got circles arranged in a closed-packed hexagonal lattice, and the circles are randomly painted black or white. Suppose I wanted to find the number of times that some pattern shows up. Say, a black triangle that's made of rows of 1,2,3 circles. I also don't want the triangles to overlap. Is there an efficient algorithm to do this? --HappyCamper 21:40, 4 December 2011 (UTC)

First, assume you have an algorithm called "Is A Triangle" that, given a circle, returns a true/false result. It return True if the circle is the point of a triangle. Of course, the algorithm can have a size parameter. So, you can give it a circle and 3 and it will return True if the circle is a corner of a 3 line triangle. Given this, finding a triangle of a specific size is easy. Just check every circle and send it to the Is a Triangle algorithm. You will get all the triangles. But, you want to avoid overlap. I assume you are looking for black triangles. So, once you find a triangle, change it to white. The circles used won't be used in any other black triangle because they will now be white. As for the Is a Triangle algorithm - that is rather straightforward. While the triangle may be of a large size, the initial circle must be the corner of the triangle. So, checking neighboring circles is easy. Unfortunately, this whole thing will not give you the maximal solution. Picking out one triangle may omit two others that overlap. -- kainaw™ 22:12, 4 December 2011 (UTC)

I think I want something a little more sophisticated because eventually I want to count things like the number of times a row of 3 black and then 4 white followed by another row of black, white, black circles show up. The brute force approach seems to be to make a matrix to represent the random array of circles, followed by a bunch of checks to ensure that the correct shape is present as the matrix is scanned. But this gets tedious to code once I have lots of patterns I want to try and match. Any other ideas? --HappyCamper 00:52, 5 December 2011 (UTC)

The unsophisticated solution is a step in the direction of finding more sophisticated solutions. Don't optimize until you have got something to optimize. Working out a simple solution will help you understand what you are talking about, and perhaps rephrase the problem. Bo Jacoby (talk) 01:17, 5 December 2011 (UTC).

To put this suggestion another way... You are requesting a specialized form of a pattern matching algorithm. Another, much more common, form of pattern matching is substring searching. For example, I want to find ADA in the string AAAADDDAADADDDAAADDA. Can I do that without checking every position in the string? No. If I never check those three positions that contain ADA, I won't find ADA (unless you have already been told that ADA is certainly in the string - but that is a whole different problem). So, you can brute force it from left to right. You can brute force it from right to left. You can brute force it by splitting it half, then split each half in half, then split those in half, etc... No matter how you do it, you must check every position. So, hopefully, you can see that you have to check your entire lattice to find a sub-lattice in the entire lattice. -- kainaw™ 03:54, 5 December 2011 (UTC)

As I wrote the above, I had an idea for what I think would be a cool research paper... The Wagner-Fischer algorithm can be adapted to find the best alignment of a short string in a long string by initializing the top/left cells of the matrix to zero instead of 1,2,3... The strings are one-dimensional (left to right only). The matrix required to solve it is two-dimensional. What if you are looking for a fuzzy match of a two-dimensional small matrix inside a large matrix? I assume the same algorithm may be used, but the matrix required to solve it must be more than two dimensions. My best guess is it must be four dimensions. Now, your lattice is three-dimensional. Each cell connects in three linear directions. I assume that with a six-dimensional matrix you could perform a fuzzy-match to locate a small lattice in a large lattice. The big problem is runtime. The real Wagner-Fischer algorithm is O(mn) for a short string of length m and a long string of length n. As the dimensions increase, so will the runtime. For a lattice, I expect it to me O(m³n³). But, proving that you can extend fuzzy matches from strings to grids to lattices would be publishable. -- kainaw™ 04:01, 5 December 2011 (UTC)

OK, I think I found a good starting point for what I want: Baker-Bird algorithm which we don't have on Wikipedia yet! --HappyCamper 05:51, 5 December 2011 (UTC)

December 5

Maths Question.

please let me know is integration difficult of differentiation? — Preceding unsigned comment added by ACCA Student (talk • contribs) 07:04, 5 December 2011 (UTC)

What? Shadowjams (talk) 07:10, 5 December 2011 (UTC)

We are not sure what you were asking, but integration is often considered to be more difficult than differentiation because, on average, for most of the functions you are likely to meet, integration produces a more complicated function than differentiation. Dbfirs 08:23, 5 December 2011 (UTC)

Differentiability is a stronger condition on a function than integrability. But the derivative of every elementary function is elementary and there's a simple algorithm to find its elementary form, but the integral of an elementary function can be nonelementary and it can be hard to find it even if it isn't. -- Meni Rosenfeld (talk) 09:10, 5 December 2011 (UTC)

From another more abstract point of view, integration is much easier than differentiation, in that the class of integrable functions is much larger than the class of differentiable functions, and much more stable --e.g. compare the usual convergence theorems for sequences or series, in both cases. --pma 14:26, 9 December 2011 (UTC)

Logic in quantum theory

The law of no contradiction is disabled in this theory, because it enable P&~P. But it's still need the law ~(P&~P) to derive theorems and make the whole theory consistent. So how could I understand this? TUOYUTSENG (talk) 08:29, 5 December 2011 (UTC)

There are a number of different interpretations of quantum mechanics, but I doubt any of them actually allow logical contradictions like that. If you are talking about quantum superposition, then the usual Copenhagen interpretation describes this in a probabilistic way. That is, if a particle is said to be in a superposition of two states, this simply means that if its state is measured, it will be found to be in one of those states with some probability p, and in the other state with probability 1-p. 81.98.43.107 (talk) 12:50, 5 December 2011 (UTC)

Scientific laws aren't proved using logical deduction. They are constructed in an ad hoc way and then tested in experiment. This is different from most mathematical proofs which depend on elementary logical rules and frequently use e.g. proof by contradiction which depends upon the law of the excluded middle. A mathematical law isn't true because it's been shown to be true by a rigorous logical argument, but because it accords with experiments. (See e.g. Grounds of validity of scientific reasoning, Validity, Falsifiability.)

Additionally, quantum physicists understand which parts of quantum theory are deterministic and which are non-deterministic, and as mentioned above they understand the probability distributions for the non-deterministic parts, so they can reason about what will happen, formulate hypotheses, and test them. --Colapeninsula (talk) 10:38, 6 December 2011 (UTC)

Hello. I don't really know enough about this subject to answer your questions, but Wikipedia has an article on quantum logic. The Stanford Encyclopedia of Philosophy has an article on "Quantum Logic and Probability Theory." Also, there is a discussion of the relation of logic to the foundations of quantum mechanics in the book Understanding Quantum Mechanics by Roland Omnès. 96.46.201.210 (talk) 04:33, 7 December 2011 (UTC)

Equivalence of two congruences

Can someone show me that 2^p ≡ 2 (mod p²) is equivalent to saying 2^{p − 1} ≡ 1 (mod p²) or explain how that can be shown? I don't seem to see it right now. Toshio Yamaguchi (talk) 10:10, 5 December 2011 (UTC)

If p is not 2, then you can divide both sides by 2. If p is 2, then you can check that the statement is trivially true.--121.74.125.249 (talk) 10:13, 5 December 2011 (UTC)

Ah, yes. ${2^{p}-2}\equiv {0}{\pmod {p^{2}}}$ and after division by 2 one gets ${2^{p-1}-1}\equiv {0}{\pmod {p^{2}}}$. Thanks. Toshio Yamaguchi (talk) 10:38, 5 December 2011 (UTC)

Is it implied here that p is prime? -- 203.82.66.201 (talk) 00:57, 6 December 2011 (UTC) Lurking WP:RD/MA, trying to learn something.

p must be odd, as if it's even and greater than zero then 2^p is divisible by 4, as is p² so neither 2^p ≡ 2 (mod p²) nor 2^{p − 1} ≡ 1 (mod p²) can be true.--JohnBlackburne^words_deeds 02:42, 6 December 2011 (UTC)

But if the statements are both false for a given value of p then they are indeed equivalent for that value of p, no ? In other words, there is no value of p, either even or odd, for which one statement is true and the other is false. Gandalf61 (talk) 09:29, 6 December 2011 (UTC)

Since these two statements are in fact the same, yes, there is no value of p for which only one of the two statements is true. Toshio Yamaguchi (talk) 10:17, 6 December 2011 (UTC)

Well, the statements are not trivially the same because the "division by 2" argument can only be used if p is odd. If p is even then you have to use John Blackburne's argument to show that they are both false and so still equivalent (in terms of truth values). Gandalf61 (talk)

December 6

Population increase percentage

I was hoping that someone would be able to calculate the population increase percentage for the following figures:

2000 Census - 18,278,559

2010 Census - 21,813,334

Thanks. --Ghostexorcist (talk) 01:19, 6 December 2011 (UTC)

(21,813,334 - 18,278,559) / 18,278,559 ≈ 0.1933, so the population of Xīnjiāng Wéiwú'ěr Zìzhìqū grew 19% during that decade. -- 203.82.66.205 (talk) 01:35, 6 December 2011 (UTC)

Thank you. --Ghostexorcist (talk) 01:36, 6 December 2011 (UTC)

Obtaining an absolute sum.

If I have a set of $N$ real numbers $x_{i}$ whose values are unknown, but I do know the values of a corresponding set of numbers$s_{i}$ given by $s_{i}=\sum _{j=0}^{N}x_{j}^{i}$ for all natural numbers $i$, is there a way of using the knowns $s_{i}$ to evaluate the sum $\sum _{j=0}^{N}|x_{j}|$. Or indeed is there any information that can be gained on the possible range of values of this sum.

Thank you. — Preceding unsigned comment added by 92.14.38.60 (talk) 10:52, 6 December 2011 (UTC)

If it is useful it is also known that all $s_{i}>0$. — Preceding unsigned comment added by 92.14.38.60 (talk) 10:54, 6 December 2011 (UTC)

The $s_{i}$ are the power sums of the $x_{i}$. Given the values of the first N $s_{i}$, you can use Newton's identities to find the values of the elementary symmetric polynomials in the N $x_{i}$. From these values, you can construct an N-degree polynomial whose roots are the $x_{i}$. If N is greater than 4 then there is no guarantee that you can find the roots of this polynomial using algebraic methods. However, you can use numerical methods to approximate the roots, and if, for example, you also know that the $x_{i}$ are all integers then numerical methods can give you an exact solution. Gandalf61 (talk) 11:29, 6 December 2011 (UTC)

For example, if N is 3, and we are given

$s_{1}=8\quad s_{2}=30\quad s_{3}=134$

we use Newton's identities to find

$e_{1}=x_{1}+x_{2}+x_{3}=s_{1}=8$

$e_{2}=x_{1}x_{2}+x_{1}x_{3}+x_{2}x_{3}={\frac {s_{1}e_{1}-s_{2}}{2}}=17$

$e_{1}=x_{1}x_{2}x_{3}={\frac {s_{1}e_{2}-s_{2}e_{1}+s_{3}}{3}}=10$

and from these we construct the cubic

$x^{3}-8x^{2}+17x-10$

By inspection, x = 1 is a root of this cubic, so we have

$x^{3}-8x^{2}+17x-10=(x-1)(x^{2}-7x+10)$

and solving the quadratic tells us that the other two $x_{i}$ are 2 and 5. Gandalf61 (talk) 11:37, 6 December 2011 (UTC)

And another method if you really do ave the values for all natural numbers you can get the billionth root of the billionth $s_{i}$ and that will very closely approximate the largest $x_{i}$, remove this from the sums and work backwards using smaller powers. This may not be quite so practical as the previous method depending on how easy it is to find the $s_{i}$ but lower values than a billion might lead to good approximations which one can iterate from. ;-) Dmcq (talk) 11:41, 6 December 2011 (UTC)

e.g. with 1 2 and 5 we have 1^10+2^10+5^10=9766650 and its tenth root is 5.00005248 at least so googles calculator assures me.

1^5+2^5+5^5 - 5.00005248^5 = 32.8359966 and its fifth power is 2.01034244

1+2+5 - 5.00005248 - 2.01034244 = 0.98960508

So there we have a fairly reasonable approximation without going anywhere near billionth powers. I'd be interested what is the best powers to choose. Dmcq (talk) 11:51, 6 December 2011 (UTC)

Use http://www.wolframalpha.com/input/?i=x^3+%E2%88%92+8x^2+%2B+17x+%E2%88%92+10 to find the roots of your polynomial. Bo Jacoby (talk) 11:17, 7 December 2011 (UTC).

December 7

3SAT Question

Hi. What is the best worst case complexity for 3SAT (that sounds weird...) I'm curious since I've got it down to O(2 ** (N/3)), and I'm wondering how much better it can be made. Thanks in advance:-) * N being the number of variables not literals. From what I can find, the best as of 2008 is around 1.4 something. This is around 1.25ish; is that worth doing something with or just trivia?209.252.235.206 (talk) 11:34, 7 December 2011 (UTC)

The goal is to get it down to O(n). That means that the n cannot be an exponent - which really means that the entire approach that is usually taken needs to be changed. The common mistake is to attack it with something like "suppose I have a machine with n switches on it..." The solution must be fixed, not an expanding thing that grows to the problem size. I've already received at least 100 solutions that go: Given n variables, get a computer with nxn registers. Hardcode memory so all the combinations of 0 and 1 are in it. Then, in O(n) look for a solution that comes out true. -- kainaw™ 13:53, 7 December 2011 (UTC)

I may be confused, so I apologize if so. But here are three things;

1.) Are you talking about/think I'm talking about solving P=NP? If so, wouldn't you mean O(n ** a)? I don't think anybody expects a linear time solution to 3sat.

2.) While P=NP is very interesting, I understand that there is some interest in algorithms for NPC problems that run in O(a ** n) for small a, I just don't know how much or how far its come. That's what my question is about.

3.) I don't understand what you mean about hard coding and the solution being fixed or about receiving 100 solutions that go a certain way. could you please elaborate, I feel as if I am missing something substantial here. 71.195.84.120 (talk) 15:20, 7 December 2011 (UTC)

I mentions O(n) as a goal - albeit an impossible one. You asked if was just trivia and, that was my attempt at an answer. Removing n from the exponent would certainly be more than trivia. You nailed why - it would get into proving P=NP. As for the hard-coded solution, that comes from many students not truly understanding P and NP. The entire solution is the solution. So, if step 1 is something like "get n Turing machines", then getting n Turing machines is part of the solution - which could be impossible for very large values of n. Students tend to think that getting a bigger machine for bigger problems is allowed. Then, I can do a 3SAT quickly. Step 1, get a huge machine that can calculate the given 3SAT in one step. Step 2, press start. I know that isn't your suggested solution, but that is a solution I receive (often multiple times) every semester. -- kainaw™ 18:44, 7 December 2011 (UTC)

Just squeezing in this as an example of someone claiming to solve 3SAT by using an expandable solution. You can see from the geek comments that it isn't a new, novel, or correct solution. -- kainaw™ 19:17, 7 December 2011 (UTC)

I think I understand the point you are making, I just don't understand how it relates to what I'm asking. Essentially, I can solve 3SAT in O(1.25 ** n), the best I've seen is O(1,45 ** n). Is this worth caring about or just some random trivia? As pertains to this question, I have no interest in P=NP and the such, and am not talking about removing the exponent. Thank you for your replies:-) 71.195.84.120 (talk) 18:52, 7 December 2011 (UTC)

I don't know the field very well, but if truly no one has done that before, then I bet it's publishable. Don't pass up a paper just because it might not be revolutionary. --Trovatore (talk) 19:10, 7 December 2011 (UTC)

That, actually, brings me to another question. I study recursion theory and set theory for fun, usually at work. I've read a good deal of research level papers, text books, etc. However, my extent with math writing is confined to my personal notebooks; further, I don't have any type of degree and am not in school. So, while I can do math (at least at a graduate level), I have no clue how to go about publishing. Do you know of any information/resources I could look at that would help me to be better able to do this? On a side note, I really hope this doesn't make me come off as a crank. 209.252.235.206 (talk) 05:46, 8 December 2011 (UTC)

Well, it's not easy. Most people who publish are currently associated with a university. I know one guy who did some very nice work while not at a university, and used it to get back in to academics (normally very unlikely, but this guy is good), but he did have a degree, and knew people who knew he was good.

Under the best of circumstances, evaluating mathematical work is difficult and takes a lot of time. So if editors are unwilling to really seriously consider submissions from someone that no one knows, it doesn't make them evil and doesn't mean that they're trying to keep high barriers to entry; it's just a cold cost-benefit analysis.

That doesn't mean you shouldn't try! I just am not quite sure how you get your foot in the door. Do you know anyone in the field personally? --Trovatore (talk) 07:37, 8 December 2011 (UTC)

No, unfortunately. For the most part, I have no formal academic experience past highschool and lack any personal contacts. All of the books I read are either on my computer or physical books I've purchased (I have a very extensive personal library), so I don't even frequent areas where I might encounter anyone in the math community. To be honest, I really love mathematics and find it fascinating; but I've never had the opportunity to pursue it in a nonpersonal context. Sadly, this seems to be hindering my ability to do anything with what I've worked on (In a larger context; not that I'm assuming there is anything worth doing with it:-)) However, I can definitely understand the reticence to spend time on material from an unknown person, looking around the internet, I'm sure math/science journals get flooded with unusable material and I would imagine it takes a while to actually review any given paper.209.252.235.206 (talk) 08:27, 8 December 2011 (UTC)

I wouldn't be surprised if an algorithmics journal might take a look at your 3SAT solver, if the argument is straightforward and clearly expressed (and correct, of course). The only one I know the name of is Algorithmica but I'd speculate that there are lots of them. If you can show that you can do correct and nontrivial work that way, maybe people would be more likely to be interested in your other stuff too. Failing that there's always the arXiv, which is publication in a sense, but gets back to the problem of how you get someone to actually read it. --Trovatore (talk) 18:10, 8 December 2011 (UTC)

Three-dimensional continuous chaotic system with an exact solution

I would like to experiment with chaotic maps, but I would prefer a system whose x, y, and z values can be determined given t (i.e., $x(t)$, $y(t)$, and $z(t)$). I have asked a similar question before, but I have not found what I am looking for. The system doesn't have to come from a natural process. Can anyone detail such a system for me? --Melab±1 ☎ 17:28, 7 December 2011 (UTC)

I assume the answer is no. Noone can detail such a system for you. Chaotic systems are characterized by not being predictable. Bo Jacoby (talk) 20:08, 7 December 2011 (UTC).

I don't think the existence of such a system can be ruled out so easily. Such a system may not exist, but this is not due to "unpredictability" of a chaotic system. That is, I believe that a large positive lyapunov exponent does not preclude analytic solutions. For instance, this paper [1] describes how exact analytic solutions to a chaotic oscillator can be used to set up secure a communication channel. (I may be missing something; it's been a while since I've studied this kind of thing in detail.) SemanticMantis (talk) 21:06, 7 December 2011 (UTC)

Oooooh, nice find, SemanticMantis! Melab-1, I seem to remember that the last time you asked (I can't find it), somebody gave an example of (I think) a 1D chaotic map that can be solved exactly. You could extend this to 3 dimensions by adding two extra variables that behave in any way you like - or maybe you would see that as cheating? 130.88.0.69 (talk) 22:50, 7 December 2011 (UTC)

I was the one who found it on MathWorld. The one-dimensional chaotic map you are thinking of is the logistic map—$x_{n+1}=r\cdot x_{n}\cdot (1-x_{n})$—which is a discrete chaotic map. $x_{n}$ has a closed-form solution when $r=-2$, $r=2$, $r=4$. --Melab±1 ☎ 00:02, 8 December 2011 (UTC)

I was obviously completely mistaken. But why not pick a simpler example? Consider a real frequency ν and the complex phase factor a=e^2πiν and the sequence aⁿ for integer values of n. If ν is rational, then the sequence is periodic, otherwise it is chaotic. Any tiny imprecision in ν is amplified until eventually the phase nν mod 1 is unpredictable. Bo Jacoby (talk) 07:29, 8 December 2011 (UTC).

I didn't know that one. I cannot use a one-dimensional system because those are discrete. --Melab±1 ☎ 22:26, 8 December 2011 (UTC)

December 8

Integration

How do i integrate (ax/(b-cx))^0.5?--95.82.51.215 (talk) 09:40, 8 December 2011 (UTC)

http://www.wolframalpha.com/input/?i=integral%28ax%2F%28b-cx%29%29^0.5dx Bo Jacoby (talk) 10:55, 8 December 2011 (UTC).

Use the substitution $x=bu^{2}/(a+cu^{2})$, then integrate by parts. Sławomir Biały (talk) 14:44, 8 December 2011 (UTC)

Time-weighted graph of sparse noisy data

I am hunting for algorithms to compare/contrast for graphing sparse/noisy data. For example, I have the data points: (0,131), (10,127), (55, 135), (123,156), (179,142), (204,131). I want to graph from 0 to 250. The goal is that the graph will be close to the real data, weighting estimated Y values to be more influenced by Y values with a nearer X value than Y values with a further X value. For example, at 100 I want to use (123,156) more than I would use (204,131) because 100 is closer to 123 than it is to 204. Unfortunately, any Googling that includes "time weighted" turns up stock pricing algorithms which are useless for this. -- kainaw™ 18:45, 8 December 2011 (UTC)

Some sort of local regression, perhaps? Qwfp (talk) 19:26, 8 December 2011 (UTC)

Thanks. I understand "regression" to mean "turning a set of data points into a formula." What I'm looking at doing is, given a set of X,Y values, pick a X for which I don't have a Y and use some sort of algorithm to estimate Y. There are several possibilities that I've already covered in this survey:

• Whatever the previous value of Y is will be the value of Y until there is a new value of Y.
• Draw a straight line between the previous and next Y. Where it crosses X with the unknown Y is what Y will be.
• Between two Y values Y1 and Y2, let the unknown Y be (Y1+Y2)/2. (mean average)
• For a given X, set Y to be the value of Y in which the mean of the distances to all known Y's is minimized. (repeat for least squared means also).

Those are some examples. I'm doing a survey on why/where each version of this is used. The big difference between this and regression is that I'm not calculating a f(x) for the data points. I'm just calculating unknown Y's for whatever X that I decide I want to use. -- kainaw™ 01:05, 9 December 2011 (UTC)

Whether we fit a specific analytic function to the data using all the points (i.e. curve fitting), or use one of your example localized algorithms, these are all broadly interpolation schemes. Another class of more local techniques is splines. Are you trying to survey what algorithms are being used today in the relevant fields, or are you just interested in what's out there? If the latter, maybe a textook like this ([2]) would be a good place to start. (sadly we have no list of interpolation schemes, only List of interpolated songs) SemanticMantis (talk) 02:14, 9 December 2011 (UTC)

Thanks. Interpolation is the keyword that I needed to find information for this survey. -- kainaw™ 03:12, 9 December 2011 (UTC)

Interpolation is the first iteration in a numerical optimization loop. The general problem you're describing is an estimation and model fitting problem subject to constraints. How sophisticated do you really want to get? For example, you can use weighted interpolation, or you can use a piecewise spline fit, or you can use a relaxation algorithm subject to smoothing constraints, and so on ad infinitum until the complexity of your curve-fitting technique dwarfs any other aspect of your project.

Here's what is important: (1) how much do you trust your data? Qualitatively, this corresponds to a "weighting function." (2) How much do you already know what your final answer should look like? This corresponds to numerical preconditioning. (3) To what extent are you willing to accept or reject outliers? This corresponds to the measure you should apply when calculating your objective function. (4) How long can you wait for an answer? This directly corresponds to the number of iterations - in other words, how many times you take the previous best-fit (say, the interpolation from the last trial), and "re-interpolate" it to make it fit even better. In the most general case, you aren't merely interpolating - you can be performing an arbitrary numerical modeling operation to your data in each pass, obtaining a better curve-fit each time.

If you just have a 1-dimensional set of points (i.e., you know y(x) for some random set of x in the range of interest), and you just want to fit a curve to it, then the least-squares method will allow you to calculate optimal fit. If the number of free parameters that describe your curve is less than the number of sample-points, you have an underdetermined problem, and you don't need to find a best-fit curve - you can just solve analytically. Nimur (talk) 03:34, 9 December 2011 (UTC)

No, that's not what regression means. There's a wide range of nonparametric regression techniques. You want to read Kernel smoother, which I think is more relevant to your needs than some of the other suggestions. -- Meni Rosenfeld (talk) 09:28, 9 December 2011 (UTC)

The Derivative of a Function

Is there a name for the class of functions which are the derivative of some everywhere-differentiable function? This is not the class of continuous functions, in light of $f(x)=x^{2}\sin(1/x)$.

Thanks, --198.213.197.177 (talk) 18:48, 8 December 2011 (UTC)

IIRC such a function must be of Baire class 1, but the converse does not hold (for example, a Baire-class-1 function can have jump discontinuities, which a derivative cannot). I don't know of any name for that exact class of functions. --Trovatore (talk) 21:08, 8 December 2011 (UTC)

This would almost be the class of Henstock-Kurzweil Integrable functions. If F is differentiable at all but countably many points, then it's derivative is HK Integrable. On the other hand, if f is HK integrable, then f is equal almost everywhere to the derivative of it's HK-integral. *This is from memory, but should be correct. 71.195.84.120 (talk) 21:31, 8 December 2011 (UTC)

Loan rates and overpayments

Driving home today I was thinking. If you have, say, a loan of £100,000 with a fixed interest rate of 5.6% over 20 years my repayment will be £703 per month. If you do the same loan over 25 years the monthly payment is less and will be £627 (simplifying things here possibly). Here in the Uk most mortgage will take overpayments instantly off the capital you owe, whereas normal payments will have the bit of interest charged before they're removed...Now to my hypothetical question. If you chose the 25 year loan and made payments of the difference between that and the 20 year load (e.g. £73 overpayment each month) would you end up paying the loan back quicker than if you'd gone with the 20 year loan? ny156uk (talk) 22:21, 8 December 2011 (UTC)

I would think it would work out the same, unless the interest rate or other changes were different. StuRat (talk) 06:57, 9 December 2011 (UTC)

... but it does depend on the exact rules about when the payment is deducted from the balance for interest purposes. Some lenders do use rules that seem unfair to the borrower, such as interest charged on the balance at the start of the year or month rather than on the average or on a daily basis. Dbfirs 09:25, 9 December 2011 (UTC)

December 9

Function

I need to find a function f(k) with k = 1, 2, ... , n subject to the following:

• f(1) is known
• f needs to match the "pattern" of another known function, g(k) and
• f(n) = g(n) but f(1) ≠ g(1)

So if g starts at some number and then increases and then decreases and ends up at 20 then f needs to start somewhere else and then increase and then decrease and end up at 20. So given g and given f(1), how do I find f? Thank you. --163.202.48.108 (talk) 10:07, 9 December 2011 (UTC)