Welcome to the mathematics section
of the Wikipedia reference desk.

Select a section:

WP:RD/MA

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.

April 9

Question about vacuous truth

Yes the question above me reminded me of a problem I've been having. If we say "For all x in A, there exist y in A such that x=y", would that be considered true? A here is empty. I know that if we have a "for all x in A, P(x)", where P(x) has no quantifiers, that would be considered true. But in here it has a "there exist" over an empty domain, although of course it comes after the "for all". Money is tight (talk) 04:07, 9 April 2010 (UTC)[reply]

Yes, the statement is true. -- Meni Rosenfeld (talk) 06:55, 9 April 2010 (UTC)[reply]

Let x be an element of A. OMG, there is no element of A, so this is a contradiction! Which means we can say absolutely anything we want to say about x. --COVIZAPIBETEFOKY (talk) 12:13, 9 April 2010 (UTC)[reply]

Informally, this property of the empty set becoms more intuitive if you phrase it as "there is no x in A for which P(x) is false". As there is no x in A - full stop - then this is always true. Gandalf61 (talk) 13:29, 9 April 2010 (UTC)[reply]

integer solutions

This question is about a statement in a book I am reading. I apologize if it is too trivial. There is an equation $c_{1}(x_{1}-x_{2})+sjdc_{1}=0$ . Here j,d are natural numbers and the rest of the terms are integers, (c1>0). The book says that by letting |x2-x1|=jd|s| we have a solution. We need |s| for some other purpose and cannot simply make the solution in terms of s. My question is how is this the solution? Thanks-Shahab (talk) 05:03, 9 April 2010 (UTC)[reply]

Was there any additional context for this equation and the importance of its solutions? Since

c_{1}\neq 0

this is equivalent to

x_{2}-x_{1}=sjd

. There's no need for absolute values to solve the equation. However, any solution also satisfies

|x2-x1|=jd|s|

, which perhaps is simply what the book needed for the rest of the argument. -- Meni Rosenfeld (talk) 07:19, 9 April 2010 (UTC)[reply]

x1 and x2 are supposed to belong to the set

\{a,a+d|s|,\cdots a+nd|s|\}

and j is among {1,...n}. Sorry for missing that part before. The proof that I am reading is of Rado's theorem (Ramsey theory)-Shahab (talk) 09:17, 9 April 2010 (UTC)[reply]

Then it looks like |s| is more important for the argument than s itself, and maybe also that the roles of x1 and x2 are symmetrical. Then indeed it may be that

|x2-x1|=jd|s|

is a more useful characterization of the solution. -- Meni Rosenfeld (talk) 09:49, 9 April 2010 (UTC)[reply]

LaTeX enumerate

\begin{enumerate} \item \end{enumerate}

I know I can label the parts whatever I want by doing \item [(b)] or whatever. But, what if I have several things that I want to be numbered in order and I have something to say in the middle. For example, the definition of a group sometimes is stated A group is a set and a binary operation satisfying the following properties: ... then the 3 properties are listed. Then, "G is said to be abelian if it also satisfies: and property 4 is listed. I have to end up doing two \begin{enumerate}'s to do this and on the second I have to manually input [4.]. That's not a big deal but what if it's more complicated like exercises in a textbook with many different sets of instructions to the different problems but all still need to be numbered in order. I don't want to have to manually type in [7.] through [56.] and what if I add a problem later, I'd have to renumber everything. What can I do? Thanks. StatisticsMan (talk) 20:11, 9 April 2010 (UTC)[reply]

I believe that you can use \setcounter{enumi}{4} at the beginning of a new enumerate. (Igny (talk) 22:00, 9 April 2010 (UTC))[reply]

Also you can look at \usepackage{mdwlist} to write

\begin{enumerate}
\item 1
\item 2
\suspend{enumerate}
text between enumerates
\resume{enumerate}
\item 3
\item 4
\end{enumerate}

(Igny (talk) 22:09, 9 April 2010 (UTC))[reply]

Cool, thanks a lot. I will try both of those out. They both seem like a great improvement over my current method. StatisticsMan (talk) 16:25, 10 April 2010 (UTC)[reply]

Eigenvector definition

Outside of the standard "a vector operation on a vector" type definition for an Eigenvector, consider an example in which a matrix is a collection of customer ratings for features of cars that they rented. A set of ratings is used to produce an Eigenvector. What does the Eigenvector represent? Is it proper to say that the Eigenvectors of the ratings simply normalize them so they can be compared? -- kainaw ™ 21:09, 9 April 2010 (UTC)[reply]

I'm not sure eigenvectors would have much significance in that kind of situation. Say we had a square matrix A where the rows are various cars and the columns are various features. If we have a column vector v, we can think of it as a weighting of the various feature scores and then Av is a vector of composite scores for each type of car using that weighting. The property of v being an eigenvector is a relationship between v and Av, but these two are indexed over different sets: v over different features and Av over different cars, so the fact that they're proportional doesn't say anything useful. Eigenvectors are meaningful when the matrix represents an map from a vector space to itself. Rckrone (talk) 02:42, 10 April 2010 (UTC)[reply]

Indeed. An eigenvector is a vector which, when transformed, is proportional to itself. A matrix of ratings like that the OP describes isn't a transformation, so the concept doesn't make sense. --Tango (talk) 15:59, 10 April 2010 (UTC)[reply]

I would assume it was meaningless as the example you have given does not constrain the matrix to be square, where as having eigenvectors does. —Preceding unsigned comment added by 129.67.119.26 (talk) 15:45, 10 April 2010 (UTC)[reply]

Usually in these situations you compute eigenvectors not of the matrix itself, but of its Gramian. If the

(i,j)

entry of X is the preference of customer i to product j (after centering and possibly scaling), then the eigenvectors of

X^{T}X

are components from which you can compose customers, and the eigenvectors of

XX^{T}

are components from which you can compose products. This is basically just PCA. -- Meni Rosenfeld (talk) 16:58, 10 April 2010 (UTC)[reply]

Symbol origins

What are the historical origins of the symbols for addition (+), subtraction (-), multiplication (x) and equal to (=)? I can understand the division one.--79.76.236.198 (talk) 22:25, 9 April 2010 (UTC)[reply]

Even though it's on a web site about English usage, this page has exactly the answers you want and appears to be well researched. By the way, if you want to read more about the history of mathematical symbols, Florian Cajori's two-volume book on the subject, published in the 1920s, is a good place to look. --Anonymous, 23:54 UTC, April 9, 2010.

April 11

Expressing an integer as a sum of powers of a prime

Hello all. This question is part of a proof that I am reading from a book. Essentially we have an integer i which has a prime p in its prime factorization. Now the book says let $\mu (i)$ be the largest integer such that ${\frac {i}{p^{\mu (i)}}}$ is an integer. I take it to mean that that $\mu (i)$ is the highest power of p in the prime factorization of i. Now the book states that $i=\sum _{j\geq \mu (i)}a_{j}p^{j}$ where $a_{j}$ 's are positive integers. I take it that it is implicitly assumed that this sum is finite, but I don't understand how to prove this statement formally. The next statement is that $1\leq a_{\mu (i)}<p$ . I don't quite follow this one either. Can anyone please help me out? Thanks.-Shahab (talk) 06:34, 11 April 2010 (UTC)[reply]

The infinite sum might make sense if the book is describing p-adic numbers - the emphasis on a prime base suggests this is plausible. Alternatively, if $j\geq \mu (i)$ is a misprint for $j\leq \mu (i)$ then the book is just saying that i has an expansion in base p with $\mu (i)$ digits $a_{j}$ , in which the most significant digit $a_{\mu (i)}$ is non-zero. Gandalf61 (talk) 08:31, 11 April 2010 (UTC)[reply]

The

a_{j}

's are positive or nonnegative? If the latter then it makes perfect sense. All the large powers will have zero coefficient, and this is just the expansion in base p. The

j\geq \mu (i)

just means that all the small powers are unnecessary because i is divisible by

p^{\mu (i)}

. All of them are

0\leq a_{j}<p

and also,

a_{\mu (i)}

can't be zero because then i would be divisible by

p^{\mu (i)+1}

. -- Meni Rosenfeld (talk) 10:45, 11 April 2010 (UTC)[reply]

Meni, what do you mean by saying that "The

j\geq \mu (i)

just means that all the small powers are unnecessary because i is divisible by

p^{\mu (i)}

". Don't the small powers contribute to the sum? Isn't it better to say

j\leq \mu (i)

. Thanks-Shahab (talk) 11:04, 11 April 2010 (UTC)[reply]

There aren't any small powers. If a number is divisible by

10^{3}

then its last 3 digits in base 10 are 0. For example,

98000=9\cdot 10^{4}+8\cdot 10^{3}

, no powers of 10 smaller than

10^{3}

involved. Exactly this also happens for expansion to base p. Saying

j\leq \mu (i)

would be incorrect. -- Meni Rosenfeld (talk) 11:15, 11 April 2010 (UTC)[reply]

Ok, thanks. But shouldn't the base be

p^{\mu (i)}

? And what does Gandalf61 mean when he says that it might be a misprint? Because the book does have a lot of those!-Shahab (talk) 11:20, 11 April 2010 (UTC)[reply]

Why should the base be

p^{\mu (i)}

? Of course we can expand the number in any base we want. For whatever reason, the book needs to use the base-p expansion. One of the things it uses to learn about the properties of this expansion (in particular, the power in which it starts) is our knowledge of

\mu (i)

.

I think Gandalf61 hasn't thought this through before he said it might be a misprint. -- Meni Rosenfeld (talk) 11:46, 11 April 2010 (UTC)[reply]

Indeed. Meni is correct - if all

a_{j}

beyond some point are 0 then the sum is just describing the base p expansion of i in which least significant

\mu (i)

digits are zero, and first non-zero digit is

a_{\mu (i)}

. Gandalf61 (talk) 10:45, 12 April 2010 (UTC)[reply]

how do you distribute poison?

Resolved

Question:

A garage has 2 vans and 3 cars which can be hired out for day at a time. Requests for the hire of a van follow a Poison distribution with a mean of 1.5 requests per day and requests for the hire of a car fiollow an independent Poison distribution with a mean of 4 requests per day.

Find the probability that on a particular day there is at least one request for a van and at least two requests for a car, given that there are a total of four requests on that day.

I tried:

There are 2 possibilities: 2 vans and 2 cars or 1 van and 3 cars. So I found poisonpdf(1.5,2), poisonpdf(4,2), poisonpdf(1.5,1) and poisonpdf(4,3) but how do I combine them?

Similar question: In the morning, the number of people entering a bank per minute has a Poison distribution with mean 3, and independently, the number of people leaving the bank per minute has a Poison distribution with mean 2.

Find the probability that during a particular minute in the morning, exactly one person will enter the bank given that the total number of people entering and leaving the bank is exactly 4.

Does that mean 3 people left the bank? poisonpdf(3,1) and poisonpdf(2,3)? —Preceding unsigned comment added by 59.189.218.247 (talk) 10:38, 11 April 2010 (UTC)[reply]

Distributing poison is illegal. I can help you distribute Poisson though :)

Let's start with the first question. Are there any additional sections to this question? Because the number of vehicles in the garage is irrelevant to the question asked - perhaps it needs to be interpreted in some special way.

I'll answer the question as written. This is a conditional probability problem - you need to divide the probability that

v\geq 1,\ c\geq 2,\ v+c=4

by the probability that

v+c=4

.

To calculate the first probability, note that the probability of the union of two mutually exclusive events is the sum of probabilities, and the probability of the intersection of two independent events is the product of their probabilities. -- Meni Rosenfeld (talk) 11:04, 11 April 2010 (UTC)[reply]

LOL OMG MY SPELLING FAIL! For the first question, that is the third part. The first two parts are:

i) Find the probability that not all requests for the hire of a van can be met on any particular day. [SOLVED: 1 - poissoncdf(1.5,2)=0.191]

ii) Find the least number of vans that the garage should have so that, on any particular day, the probability that a request for the hire of a van for that day has to be refused is less than 0.1. [SOLVED using graphic calculator, table of poissoncdf(1.5,X)>0.9, answer is 3.]

I think that the probability that v + c = 4 would be poissonpdf(5,4), correct? Which events are mutually exclusive? I know the requests for vans and requests for cars are independent. THANKS! —Preceding unsigned comment added by 59.189.218.247 (talk) 11:32, 11 April 2010 (UTC)[reply]

The events that are mutually exclusive (and together exhaust the requirement

v\geq 1,\ c\geq 2,\ v+c=4

) are: The first is v=2, c=2. The second is v=1, c=3. So you need to sum the probabilities of the first and the second. To find the first, for example, you need to multiply

P(v=2)P(c=2)

. -- Meni Rosenfeld (talk) 11:51, 11 April 2010 (UTC)[reply]

Solved! THANKS! May come back with more questions soon, hehe.

April 12

Simple way to weight average ratings by total ratings?

I've got a website where users can rate items from 1 to 5. The site won't get a lot of traffic, and I expect the "total ratings" range for the items to be as high as 100 and as low as 4 or 5. Each item can be rated on an integer scale of 1 to 5. I'd like to be able to show a top 10 list of best-rated items, but because of the wide variance in total ratings I feel this needs to be weighted in some fashion to favor items with more votes. Unfortunately, I've never taken a stats class and really don't know what to do. Could some of you kind folks please suggest some relatively simple approaches to solving this problem? Thank you! (Calculations will be done in PHP/MySQL if that's relevant, though I doubt it'd matter) 59.46.38.107 (talk) 00:52, 12 April 2010 (UTC)[reply]

You should just use a simple cut-off. For example, list the top rated products of those with 10 or more ratings. StuRat (talk) 00:54, 12 April 2010 (UTC)[reply]

I agree, a simple cut-off is best. The number of ratings doesn't say anything about the quality of the product, just the confidence you can have in the average weighting, so you don't want to take the number of ratings into account for a top 10 list. The products with only a handful of ratings are just as likely (given no additional information) to be underrated as overrated. If you want to do something more complicated, you could do a variable cut-off and choose the cut-off for each product based on the variance of the ratings for that product. If you have had 5 ratings and they have all rated a product 3 then you can probably have more confidence in that rating than the rating of a product with 20 ratings of 1 and 20 ratings of 5. I'm not sure what function of variance would be best. To be honest, I think a simple cut-off is better, a variable one would be being complicated for the sake of it rather than to get significantly better results. --Tango (talk) 01:17, 12 April 2010 (UTC)[reply]

To me, a small number of identical ratings would indicate the likely use of sock-puppets, by one individual. StuRat (talk) 02:10, 12 April 2010 (UTC)[reply]

A product with only a handful of ratings, given what those ratings are, is not as likely to be underrated as overrated. A product with a few high ratings is more likely to be overrated than underrated. This is basically regression towards the mean. In other words, if your prior is that the product is average, the more evidence you have that the product is good, the higher your assessment of its expected quality. Thus a product with many good ratings should be placed higher than a product with a few excellent ratings (depending on the exact numbers, of course).

Personally I would use a parametric model with Bayesian updating for each product, but I guess that falls outside what the OP can easily work with. -- Meni Rosenfeld (talk) 08:34, 12 April 2010 (UTC)[reply]

Thank you so far. If I go with a simple cutoff should that limiter be a function of the total userbase so that as the userbase grows more votes are required? Or should it be a fixed value? 59.46.38.107 (talk) 01:27, 12 April 2010 (UTC)[reply]

I think you might want to increase the cutoff number once you have more reviews. You don't necessarily need to code in a formula for this, though, just have a fixed number which you edit and change from time to time. Using a formula is more likely to introduce problems. If you're determined to use a formula, though, you could only compare those products with more than the median number of reviews. StuRat (talk) 02:08, 12 April 2010 (UTC)[reply]

As a rule of thumb, if you have about 30 values (from a normal distribution), average and standard deviation become somewhat reliable measures. So you can probably stop increasing the cut-off once it reaches 30. This will also give great new products a chance to show up eventually. --Stephan Schulz (talk) 08:40, 12 April 2010 (UTC)[reply]

You might want to look into the IMDB system since they have some of the same issues. As I recall, they use the straight average when the number of votes is high enough and otherwise they use a weighted average. The exact formula is on their website somewhere.--RDBury (talk) 10:12, 12 April 2010 (UTC)[reply]

There's a precise answer to your original question here: [1] I don't know enough statistics myself to check it, though. Paul (Stansifer) 21:38, 14 April 2010 (UTC)[reply]

That is an answer to a different question, where ratings are positive\negative rather than 1-5. Also, it gives one particular frequentist way to think about the problem, which is neither the only nor necessarily the best way. I think using the expectation of the posterior distribution will give better results. -- Meni Rosenfeld (talk) 09:38, 15 April 2010 (UTC)[reply]

The code example is for a two-point rating scale, but I believe the technique can work for 1-5. Paul (Stansifer) 14:13, 15 April 2010 (UTC)[reply]

I don't see any obvious way to extend it, and by the time we get to non-obvious ways we may as well start from scratch. -- Meni Rosenfeld (talk) 18:35, 15 April 2010 (UTC)[reply]

Equations on cartesian planes with interesting properties

Hi. The following functions can be graphed using a graphing calculator (or is there some kind of online/HTML program that can do that?), but have interesting properties, such as having Y values with no X values, looking like a seismograph, etc. My question is what are some equations with similar properties, and what causes them? This is not homework.

y=x\sin(0.5\pi )^{2}-2x^{-1}/9{\sqrt {x-\tan(180/\pi )}}

y=\sin(\cos(\tan(89x+3)))+\sin(x+\pi )^{-1}

y=\tan(60x)(\arctan 30x)

y=\tan(\tan(x^{2}))

y=\sin(\cos(x^{2})x^{-1})-\tan(x^{2})/\arcsin(x)

y={\sqrt {(x-\sin(x^{2})+x^{-1}-3x)^{3}}}

Thanks. ~A H 1^(TCU) 01:14, 12 April 2010 (UTC)[reply]

Y-values without x-values is very common. (The graph of the constant function y=0 has no x-values when y is not zero.) X-values without Y-values means that the function is not defined for some x-values. For example is y=1/x not defined when x=0. This function has a Pole for x=0. The functions in your examples have poles in the x-values where y is not defined. Bo Jacoby (talk) 13:08, 12 April 2010 (UTC).[reply]

For plotting online, try FooPlot and Wolfram Alpha. (I prefer the former for most straightforward plotting, although Alpha will do, e.g., implicit functions.) 94.168.184.16 (talk) 23:28, 12 April 2010 (UTC)[reply]

Set theory

if S = {i | 0<i<=50}, |S| = 10, A and B are subsets of S, |A|=|B|=5, sum of all integers in A is equal to that of all integers in B, then prove that there exist atleast one such pair A and B.Rajeev 26987 (talk) 07:22, 12 April 2010 (UTC)[reply]

If

S=\{i|0<i\leq 50\}

then

|S|\neq 10

. Did you mean

S\subseteq \{i|0<i\leq 50\}

? -- Meni Rosenfeld (talk) 08:09, 12 April 2010 (UTC)[reply]

I guess A and B have to be disjoint? If not, let A be any subset of S, with B=A. Staecker (talk) 10:56, 12 April 2010 (UTC)[reply]

Think of the elements of A and B as pairs. For each pair A_j and B_j for j=1 to 10, if j is even, ensure that A_j=B_j+1. If j is odd, ensure that A_j=B_j-1. So, there are 5 cases where B_j is one more than A_j and 5 where it one less. They cancel each other out, making A and B sum up to the same value. -- kainaw ™ 12:29, 12 April 2010 (UTC)[reply]

Subconical shapes?

What exactly is a subconical shape? I've read many descriptions of individual Native American mounds that speak of the mound as being subconical; however, as you can see from the picture of the subconical Dunns Pond Mound, this apparently can mean "vaguely round and slightly raised in the middle", and definitely not very much like a Cone (geometry). Nyttend (talk) 11:33, 12 April 2010 (UTC)[reply]

Let me rephrase the question — is there some official definition of "subconical" or "subcone"? Thanks. Nyttend (talk) 11:36, 12 April 2010 (UTC)[reply]

Well, Wiktionary has a definition, but it just says "somewhat cone shaped", so not very helpful; Webster's says "slightly conical", which is just as useless. Googling random examples, "subconical" seems to often used to describe the shape of a flattened or truncated cone - possibly what we maths types would call a conical frustum. Gandalf61 (talk) 13:27, 12 April 2010 (UTC)[reply]

I was thinking of the shape a powder takes when dumped at a central point onto a plane, like the sand in the bottom of an hour-glass. This yields a slightly bowed-out cone. Salt storage facilities shape their containers to match this form. Here's an example: [2]. StuRat (talk) 01:55, 13 April 2010 (UTC)[reply]

Lowering Summed Indices for Tensors

Let's say we have a tensor $A_{\alpha \beta }$ . The tensor is defined as $A_{\alpha \beta }=g^{\lambda \gamma }S_{\alpha \gamma }T_{\lambda \beta }$ where $S_{\alpha \gamma }$ and $T_{\lambda \beta }$ are tensors with $g^{\lambda \gamma }$ the inverse metric, and I want to lower indices of the inverse metric. How do I achieve that, since the inverse metric is summed over.~~The Successor of Physics~~ 13:29, 12 April 2010 (UTC)[reply]

You can move those indices down and move the other indices they are contracted with up. Count Iblis (talk) 17:01, 12 April 2010 (UTC)[reply]

A_{\alpha \beta }=g^{\lambda \gamma }S_{\alpha \gamma }T_{\lambda \beta }=g_{\lambda \gamma }S_{\alpha }^{\gamma }T_{\beta }^{\lambda }=S_{\alpha \lambda }T_{\beta }^{\lambda }=S_{\alpha }^{\lambda }T_{\lambda \beta }

. Bo Jacoby (talk) 20:56, 12 April 2010 (UTC).[reply]

Probability

I have b buckets that each can hold n items, and I have i kinds of items. I fill every bucket with unique (different kinds) of items. Items need not be unique across buckets. What's the probability that there are at least l of each kind of item in the buckets? I want to get an idea of the plausibility of untrusted distributed backups but it appears I fail at mathematics. --194.197.235.240 (talk) 19:17, 12 April 2010 (UTC)[reply]

You mean you're going to scatter these items around the buckets randomly? If yes, how do you know a given kind of item doesn't occur in a bucket more than once? Really aren't you better off populating the buckets deterministically so you can control where and how often each item is backed up? Maybe you also want to read about erasure codes rather than relying on pure replication. 66.127.52.47 (talk) 23:42, 12 April 2010 (UTC)[reply]

A "bucket" is one computer, the computer downloads random unique blocks of the backup. I can't populate deterministically because I assume most of the world hates my backups and a large fraction of the participating computers are cheating. This scheme likely isn't any good, but it hurts my feelings I can't solve it. --194.197.235.240 (talk) 14:51, 13 April 2010 (UTC)[reply]

That doesn't sound all that easy to do exactly, but I'll see if I can figure it out if I get some time later. The case where the # machines is large might be easier: let's see. The probability that a given bucket has a given block is n/i. So the probability p that at least l buckets have that block is given by the cdf of the binomial distribution on b buckets. The events for the different blocks being replicated l times are not independent since replicating one such block decreases the amount of space left for the others. (There may be some fancy distribution related to urn problems that exactly accounts for this--I'm not very knowledgeable about such things). But if n*b is much larger than i, maybe you can approximate as p**i. The other thing you can easily do is run some random simulations instead of trying to calculate the probability precisely. 66.127.52.47 (talk) 21:54, 13 April 2010 (UTC)[reply]

Taylor-like Series

I was thinking about smooth functions $f:\mathbb {R} \to \mathbb {R}$ , and I defined an operator ${\mathfrak {F}}$ ; given by

{\mathfrak {F}}(f):=\lim _{n\to \infty }\sum _{k=0}^{n}{\frac {d^{k}\!f}{dx^{k}}}{\frac {x^{k}}{k!}}.

This operator has a nice property. It can be shown that

{\frac {d}{dx}}{\mathfrak {F}}(f)=2{\mathfrak {F}}\left({\frac {d}{dx}}f\right).

Working out some explicit examples, one the sine, cosine and exponential functions gives

{\mathfrak {F}}(\sin x)=\sin(2x),\ {\mathfrak {F}}(\cos x)=\cos(2x),\ {\mathfrak {F}}(e^{x})=e^{2x}.

I used Matlab to get these last identities. It doesn't seem obvious to me, for example:

{\mathfrak {F}}(\sin x)=\sin x+x\cos x-{\frac {x^{2}}{2}}\sin x-{\frac {x^{3}}{6}}\cos x+\cdots .

I have a couple of questions:

How do we prove the expression for, say, the sine function?
What is the domain and range of this operator? (I think that if $f$ has a convergent power series in a n'hood of $x_{0}\in x$ then ${\mathfrak {F}}(f)$ converges in a n'hood of $x_{0}$ ).
Is this operator already known and studied? If so, does it have any uses?

•• Fly by Night (talk) 19:39, 12 April 2010 (UTC)[reply]

First question: if you plug in f(x)=e^(ax) to your formula, you see that

{\mathfrak {F}}(f)(x)=e^{2ax}

. Now note that your operator is linear in f, and sin x is a linear combination of exponentials. 129.67.37.143 (talk) 21:48, 12 April 2010 (UTC)[reply]

OK, so it's quite straightforward for the exponential case:

{\mathfrak {F}}(e^{\lambda x})=e^{\lambda x}+\lambda xe^{\lambda x}+{\frac {(\lambda x)^{2}}{2!}}e^{\lambda x}+{\frac {(\lambda x)^{3}}{3!}}e^{\lambda x}+\cdots =\left(\sum _{k=0}^{\infty }{\frac {(\lambda x)^{k}}{k!}}\right)e^{\lambda x}=e^{\lambda x}\cdot e^{\lambda x}=e^{2\lambda x}.

but since I'm only considering real functions and you need complex function to make sine from exponentials:

2sin(x)=i(e^{-ix}-e^{ix})

, I don't see this can prove it. •• Fly by Night (talk) 22:11, 12 April 2010 (UTC)[reply]

For analytic functions you can sum the Taylor expansion and show that

{\mathfrak {F}}f(x)=f(2x)

Count Iblis (talk) 23:18, 12 April 2010 (UTC)[reply]

just to give a bit more of a hint, show that

{\mathfrak {F}}f(x)=f(2x)

when f is x^n, then extend to power series by linearity 129.67.37.143 (talk) 08:29, 13 April 2010 (UTC)[reply]

While you may be working with real functions, it is often possible (and in many cases easier) to work in the realm of complex functions, and as long as your functions are analytic in a region including the real axis, your proofs are valid for the real function as well. The identities between exponential and trigonometric functions is a good example. (Analogously, you might have a function acting on the integers, but to prove some property it's easier to extend the function into the reals.) Confusing Manifestation(Say hi!) 00:58, 13 April 2010 (UTC)[reply]

Thanks, now what about questions 2 and 3? •• Fly by Night (talk) 19:02, 13 April 2010 (UTC)[reply]

Adomian decomposition method

Hello Math Reference Desk. I have recently come across the Adomian decomposition method in a paper I am reading. I have never heard of this technique, and our article is very vague and stubby. Can anyone enlighten me on the purpose, utility, and general procedure for Adomian decomposition? I understand it is a "semi-analytic" method to solve PDEs, but I'm not clear whether that means it's "analytic" or "numerical." Probably the most important part of my question: is this method common/widespread, or is it an esoteric technique? Thanks, Nimur (talk) 23:22, 12 April 2010 (UTC)[reply]

The Wikipedia article doesn't say much, but that other site has some links about it. 66.127.52.47 (talk) 23:50, 12 April 2010 (UTC)[reply]

April 13

Three Dimension

If P (a,b,c) and Q (x,y,z) are two points in three dimensional space, how can we find equation of line PQ.

There are many methods. See system of linear equations. -- kainaw ™ 03:41, 13 April 2010 (UTC)[reply]

I think the simplest method is the vector equation: r = OP + λPQ where r is the position vector of any point on the line, OP is the vector from the origin to P, and PQ is the vector from P to Q. The parameter λ indicates how far along the line we have travelled. λ = 0 at point P, λ = 1 at point Q etc. Other people will have different preferences, and the various methods are all equivalent. Dbfirs 08:04, 13 April 2010 (UTC)[reply]

If you just need a Cartesian equation, you can eliminate λ to give: (x - x₁)/a = (y - y₁)/b =(z - z₁)/c where the co-ordinates of point Q are (x₁, y₁, z₁) Dbfirs 08:13, 13 April 2010 (UTC)[reply]

Complex logarithm

S is an arbitrary set (being a sub-set of the complex plane), and L is a function satisfying: exp(L(s))=s for every s in S. Does the continuity of L in S allow us to infer that L is also differentiable in S?

Note that if S is a domain then the answer is trivially positive.

Note also that L is differentiable in S if and only if:

For every s in S there exists a number n (intended to constitute the value of L'(s)), such that for every ε > 0 there exists a δ > 0 such that every x in S which satisfies $0<|x-s|<\delta$ , satisfies $\left|{(L(x)-L(s)) \over (x-s)}-n\right|<\varepsilon$ .

77.124.141.144 (talk) 13:21, 13 April 2010 (UTC)[reply]

By "convergent series", do you mean "convergent sequence"? Michael Hardy (talk) 15:33, 13 April 2010 (UTC)[reply]

yes. 77.124.141.144 (talk) 16:00, 13 April 2010 (UTC)[reply]

If S is arbitrary, it doesn't necessarily make sense to talk about whether or not L is differentiable - you want the domain to be open. In this case, try proving that on each connected component of S, L is given by some fixed branch of the log function (making it holomorphic). If not, you should be more clear about what you mean by "differentiable." 136.152.163.70 (talk) 16:29, 13 April 2010 (UTC)[reply]

L is differentiable in S if and only if:

For every s in S there exists a number n (intended to constitute the value of L'(s)), such that for every ε > 0 there exists a δ > 0 such that every x in S which satisfies

0<|x-s|<\delta

, satisfies

\left|{(L(x)-L(s)) \over (x-s)}-n\right|<\varepsilon

.

77.124.141.144 (talk) 17:33, 13 April 2010 (UTC)[reply]

If L is continuous at s then for every ε>0 there exists δ>0 such that |L(s)-L(x)|<ε for all |s-x|<δ, which means there's a δ for which L(x) is always in the same branch as L(s), so in that neighborhood L is holomorphic and satisfies that definition you provided for differentiability. Rckrone (talk) 18:48, 13 April 2010 (UTC)[reply]

How can you determine that "L is holomorphic" when L is unnecessarily defined in a domain (=connected open set)? 77.124.141.144 (talk) 20:17, 13 April 2010 (UTC)[reply]

Ok to be more accurate L is the restriction to S of a function f that's holomorphic in a neighborhood of s (f can be set equal to an appropriate branch cut of the log function inside the disk around s). That satisfies the definition you provided for L being differentiable in S at s. Rckrone (talk) 20:51, 13 April 2010 (UTC)[reply]

Thank you. 77.124.141.144 (talk) 21:27, 13 April 2010 (UTC)[reply]

Reuptake of a question 2d travel distance and energy expenditure vs. 3d - ramblings

Hi )again(

I looked up an old question I once posted and saw that I wanted to pose some insert extra questions and explanations to my point that was never answered.

I have pasted the original question and answers/comments here after the line... can someone help me to elaborate on my last questions/postulations everything once more.

I'm still in the process of rereading and trying to pose a better question with the 'old' comments in mind, but till then I only want to ask you for a bit help to explore the subject more.

The headline could also be 4d vs 3d creatues

Thanks....

About 2 D creatures traveling on a 2 D plane seen from a 3 D point of view I've got this strange theory that I conjured out of thin air som 15 years ago, have there been anybody else than me thinking about this stuff.

I postulate hereby that C a 2D creature's fastest way (like in shortest/less resource expenditure) of traveling (in an XY plane) from point A to point B would be to travel in one direction (X or Y) (not distance AB) until it would be at the distance AB - (A - (X or Y)) = B and then the distance B.

This way the creature C would only have to change direction of travel (90 degree change) once.

Try to think about this and and tell me how much further would 2 D creature have to travel compared to a 3D (capable) creature, my answer is squareroot 2 (appr. : 1.4) times more.

Reason: while the 2D creature could change direction of travel (X or Y) for every second or mm (or whatnot) that it went, this would take even more time/resources ..stop/change direction etc.... than it would to just travl the distance in the X direction and then after that in the Y direction....one start/stop/start/stop

Relate this to a 3D creature like us in a 4D world....and the answer would be 0.5 times the value of pi.....and bring in the double slith photon/electron experiments and other relativistic points... anybody got any thoughts about this...?

Could this be elaborated a bit more? [Azalin1999]

Uh. Perhaps you should phrase your question better. Are A and B points or lines? You use them as both. What's X and Y? And if it travels from A to B in a straight line, it doesn't ever need to change its direction. --BluePlatypus 18:05, 15 March 2006 (UTC) I think maybe I see what he's getting at, but it doesn't really have anything to do with 2 vs. 3 dimensions. It sounds to me like he's describing the Manhattan distance. At least in the first part where he's talking about 2 dimensions. If you compare the Manhattan distance (let's call it m) with the ordinary, Euclidean distance (d), between any two points in a Euclidean plane, it's not too difficult to show that . But I have no idea where he's getting the factor from for three dimensions. In three dimensions, you have . More generally, in n dimensions, . Nor do I see what it has to do with quantum mechanics or relativity. Chuck 18:40, 15 March 2006 (UTC) Hi again I'm the one who phrased the question. A little note about myself. Never did score high in maths and equations but I'm really curious about this 'theory'. Much thanks for the link to the 'manhattan distance' article, I think I remeber reading about it some years ago. My native tounge is Danish so that's my excuse for the inaccurate phrasing.

I originally made some drawings on a XY crossed paper to illustrate the theory. And I had a really hard time to explain my arguments for those I presented it to (mostly indiferrent friends). And I still have difficulties atm. because the thing I would like to verify is that it would be possible to apply something like this 'manhattan distance' to distances in a 3D world seen from the perspective of a fourth dimension. Which should be possible. Basically like --BluePlatypus went about distances in an euclidian plane...

The distance 1/2 Pi was derived from projecting a imaginary path (distance traveled) through 4D space compared to what a 3D creature would have go by not using the 4th dimenson...like a 2D creature can't (see, thus) travel the path that a 3D creature can. In regards to the 'Manhattan Distance' this would be akin to a race between a cab an a helicopter going over the cityblocks.

Too bad your friends are indifferent; this stuff is fun! As Chuck wrote above, yes, you can define Manhattan distance in 3D, and you don't even need a 4D perspective to do it. I'm not sure where the pi is coming from. As for bringing in modern physics like quantum mechanics and relativity, let's just say that they're not really compatible with a Manhattan metric. If you lived in a world where the physics was affected by a Manhattan metric, you would easily be able to experimentally determine the coordinate axes you lived on, whether you're a 2D or a 3D creature. But we've never observed any such special directions in space. Melchoir 19:30, 15 March 2006 (UTC) That's an understatement! :) If all directions weren't equivalent, you wouldn't have conservation of angular momentum, and that'd really yank out the carpet from under physics-as-we-know-it. --BluePlatypus 20:08, 15 March 2006 (UTC) OK, I kind of see where you're going here. First of all, it's important to remember that the factor in 2 dimensions is a maximum; it doesn't hold for all pairs of points. For example, if you're travelling from (0,0) to (5,5), the person constrained to taxicab geometry has to travel 10 units, but the person who can travel in any direction only has to travel units, and the person limited to taxicab geometry has to travel times farther in that particular case. However, if you're traveling from (0,0) to (7,24), the Euclidean traveler has to travel 25 units, but the taxicab traveler only needs to travel 31 units--just 1.24 times further than the Euclidean traveler, which is considerably less than . And of course, if you're going from (0,0) to (13,0), both people travel the same distance. The analagous situation in three dimensions, it seems to me, is someone who can travel in any one of six orthogonal directions (which we might call "north," "south," "east," "west," "up," and "down," but it's important to remember here that these are idealized directions where all north-south lines are parallel with each other and do not meet, as are the east-west lines, and also the up-down lines; and not the directions as defined on the earth, where the "north" lines all meet at the north pole, the "south" lines all meet at the south pole, and the "down" lines meet at the center of the earth). In this case the maximum factor between the distance of the taxicab traveler and the distance of the Euclidean traveler would be , for example going from (0,0,0) to (5,5,5) the taxicab traveler has to move 15 units, as opposed to the Euclidean traveler's units. But as before, that's a maximum: in going from (0,0,0) to (3,4,12) the taxicab traveler goes 19 units to the Euclidean traveler's 13, but . It's possible to choose a pair of points where the taxicab traveler's distance is exactly times as long as the Euclidean traveler's, but that's only because such a pair of points can be found for any number x such that , which happens to satisfy. The "car vs. helicopter" analogy is an interesting way to think about it, but at the same time it's misleading because you don't actually have to move in the 3rd dimension for this to happen. You can have one traveler who can move in any direction, and one traveler who is limited to moving in a set of orthogonal directions, and still have both of them confined to a plane, so it's not really an issue of one person being constrained to two dimensions while another can move in three (or three vs. four, or four vs. five, etc.) Chuck 20:33, 15 March 2006 (UTC) You're Chuck making some good points. But what if we assume that in our (unlimited) reference 3D space we are looking down on the 2 plane (which could be from any arbitary reference point/perspective) let's say head on, straight down.

Let's asume some more - Our little 2D creature can only observe (look) through either the X or the Y, and thus only observe it's destination when its in line with either the x axis of the destination or th Y axis, whichever comes first, depending on which route it took.

From the 3D POV this would satisfy my squareroot 2 clause about a 3D being would be able to go the shorter distance right? Because it can sort of observe the direct line of vision...X & Y combined.

Now if the 2D creature were able to in some way observe the destination it could of course just travel the direct route. But this would only happen after it had moved all the way along either the X or Y axis to be in line with the destination. If this 2D thing were sentinent the percieved distance the 2D being traveled would be? the squared X+Y which is less than the distance it really took if a 3D being measured...also there are 2 routes that are the same distance but starting with etiher going out of the X or the Y axis...

Relate this to a 3D world...(damn crunching)hmm non-euclidian geometry..........Spherical trigonometry

Thanks again

fractals and harmonics

One phenomenon of a harmonic is that it consists of multiples of the base radio or audio signal only at a higher frequency. Thus the shape of a harmonic of a sinusoidal wave form will be sinusoidal and the shape of a harmonic of a triangular wave form will be triangular. The difference between fractals and harmonics then seems to be the difference in what happens in space and what happens in time. Can anyone elaborate or point me to an article that elaborates on this idea? 71.100.1.192 (talk) 22:55, 13 April 2010 (UTC)[reply]

Fractal antenna might be of interest, since that combines both fractals and radio waves. StuRat (talk) 05:52, 14 April 2010 (UTC)[reply]

equations that scale and fractals

No matter how large or small the value of x above zero in the equation x^(4/3) one sees the same curve. How is this phenomenon related to fractals? 71.100.1.192 (talk) 23:39, 13 April 2010 (UTC)[reply]

It's rather like saying that all parabolas are geometrically similar (which they are). All fractals show some form of similarity at countably infinite discrete magnifications, though none are continuously similar (with uncountably infinite magnification similarities) like the parabola. For some fractals there is exact similarity at repeated levels, for others the similarity is not precise. From a mathematical point of view, structures like coastlines and (woody) trees might be described as "pseudo-fractals" because they are similar at only finitely many magnifications, and the similarity is far from exact, with different structures at each similarity level. Perhaps an expert on fractals can check my claims. Dbfirs 20:55, 14 April 2010 (UTC)[reply]

April 14

Randomness Testing

The following string of 44 digits represents final digits of a sequence of 33-digit results on the calculator that comes with Windows98 (Specifically: The 4th root of 17797577777.77...7 minus that of 17797577777, where the 7s after the decimal point range from 1 to 44, where calculation is consistently done with the square root operation, where beyond the 20th term the whole and decimal parts are added to each other and beyond the 30th term this entails a further addition of 7*10^-31, 7.7*10^-31, etc.). This sequence was arrived at without discarding previous similar data (i.e., the claim is that this was not part of a data-mining operation).

$38297838339867556722539777859777712092576764$

Now, I chose to identify the salient feature of this string to be that three of our digits are missing through precisely 33 terms, the last to arise being 4 at the 44th, and the digit 0 being one of the other two to allow me to notice this all; and a random sequence of digits with this description results with probability 3.132*10^-7.

I have more inaccurate digits to work with--the penultimate, third from last, etc.--and I'm wondering if there is a specific best approach to finding a non-random pattern or other indication. This may be the sort of thing I should know by now, but I don't. Any help would be appreciated. Thanks, and sorry I couldn't re-type the whole sequence including non-final digits after my flub with this laptop touchpad.Julzes (talk) 01:13, 14 April 2010 (UTC)[reply]

Are you basically asking about checking whether a coin is fair? 66.127.52.47 (talk) 09:55, 14 April 2010 (UTC)[reply]

I guess my own calculation on the final digits is close to that, but I was looking for something perhaps a little deeper along the lines of picking a signal of any type out of noise. I don't suppose I'm looking for something simple enough to be fully described in an encyclopedia article, but perhaps a description of the basic theory behind something hard with a link to an adequate tool based upon it. Note that the description of the method for obtaining the sequence is given in full. If someone wants to replicate and analyze it and report back on that, that would be almost equally interesting as telling me how to do it myself.Julzes (talk) 14:17, 14 April 2010 (UTC)[reply]

If you want to get a signal from data you have to formulate your hypothesis before you examine the data. You can always retrofit properties that make any given data meaningful or surprising. When I expand 1/3 to 10 digits, I get 0.333333333 - the chance for that string of digits is 10^-10 (or 1, depending on how you see it). Note that nearly all real numbers are normal numbers, meaning that the probability that the decimal representation of a (uniformly) random real number contains an encoding of the full text of Hamlet and the dedication "For Lizzy, with love! Your Oxi!" is 1. -Stephan Schulz (talk) 14:54, 14 April 2010 (UTC)[reply]

Out of curiosity, just what do you mean by "a uniformly random real number"?

(I think a complete answer would be very long. There's a rather natural notion of what it means for a real number to be, roughly speaking, random against all computable tests — three fairly natural and distinct formulations, by Kolmogorov, by Martin-Löf, and a third I don't remember, turn out to be equivalent. However, by requiring randomness against wider classes of tests, you get ever stronger notions, each of which still holds for almost all reals. My sense is that there is no coherent notion of what it means for an individual real to be "truly" random. This is a similar conundrum to the one about what, if anything, it means to be a definable real number.) --Trovatore (talk) 01:55, 16 April 2010 (UTC)[reply]

I was imprecise, in that I should have restricted it to some finite, non-empty interval. In that case, the notion is clear (in my head ;-). --Stephan Schulz (talk) 02:01, 16 April 2010 (UTC)[reply]

Well, no, the finiteness of the interval is not really the point. Everything I said above holds without modification on [0,1]. --Trovatore (talk) 02:04, 16 April 2010 (UTC)[reply]

Oh, wait, I didn't see that you specified "the probability that ... of a random real number:. OK, that's different; that's linguistic shorthand for something else, and doesn't imply that you have a notion of what it means for an individual real to be random. My apologies; I misinterpreted you. Too bad, though, in a sense, because it's a very interesting subject. --Trovatore (talk) 02:09, 16 April 2010 (UTC)[reply]

Finding patterns can be extremely difficult (cryptanalysis amounts to that), but one simple approach for the example you gave would be to find a Markov chain that describes the data. See also dynamic Markov compression. 66.127.52.47 (talk) 15:37, 14 April 2010 (UTC)[reply]

I guess my hypothesis is that whatever signal there may be from a purely mathematical standpoint in the array of inaccurate 6 or 7 final digits is pretty much entirely in the final digits. Apparently, according to Stephan Schulz, I've ruined the final digits by noticing a pattern after seeing the data. Thanks for the article suggestions, unnamed number person.Julzes (talk) 14:27, 15 April 2010 (UTC)[reply]

Diophantine equation

Using the equation ${1 \over x}+{1 \over y}={1 \over n}$ , I have found that the number of solutions when n is a power of any prime (n^x) to be: $xn-x+1$ . Similarly, if n has 2 prime factors, $n=p_{1}^{x}*p_{2}^{y}$ , the number of solutions is: $(2xy)n^{2}+(4xy+x+y)n-(2xy+x+y-1)$ and if n has 3 prime factors: $(4xyz)n^{3}-(10xyz-2xy-2z)n^{2}+(12xyz-4xy-4xz-4yz+x+y+z)n-(4xyz-2xz-2xy-2yz+x+y+z-1)$

However, I basically just arrived at these equations through trial and error. Where are they coming from, and how can I generalize this? 129.219.184.186 (talk) 02:02, 14 April 2010 (UTC)[reply]

Are you sure about those formulas? For 1/x + 1/y = 1/p^k I find that there are only 2k+1 integer solutions regardless of what p is. They are the pairs (p^k(pⁱ+1), p^k-i(pⁱ+1)) for all 0 ≤ i ≤ k, as well as those pairs with x and y reversed. Rckrone (talk) 06:32, 14 April 2010 (UTC)[reply]

Oh wait, I only considered positive x, y. Allowing negative values adds an additional 2k solutions: (-p^k(pⁱ-1), p^k-i(pⁱ-1)) for all 0 < i ≤ k and their reverses. That makes a total of 4k+1 integer solutions. Rckrone (talk) 06:47, 14 April 2010 (UTC)[reply]

Thinking more generally about the shape of the graph in the x-y plane, we can conclude that the number of integer points can never exceed 4n-3, which rules out a quadratic or higher in n. Rckrone (talk) 08:08, 14 April 2010 (UTC)[reply]

I get a parametric solution as x=(a+b)ak, y=(a+b)bk, n=abk. You can assume a and b are relatively prime and you can then determine all the solutions for a given n if you know its factorization.--RDBury (talk) 20:20, 14 April 2010 (UTC)[reply]

Actually there is a simpler solution: x=n+a, y=n+b where ab=n². That gives the number of solutions as d(n²), the number of divisors of n², if you count only positive solutions, and 2d(n²)-1 solutions if you allow negatives. (You can eliminate a=b=-n since that produces x=y=0 which is impossible.)--RDBury (talk) 03:18, 15 April 2010 (UTC)[reply]

Wow, nice. Rckrone (talk) 06:46, 15 April 2010 (UTC)[reply]

RSA

Reading about the number theoretic details of the RSA algorithm, I know that if n=pq (p and q are two large distinct primes) is factored, then $\phi (n)=(p-1)(q-1)$ can be easily computered and then using the euclidean algorithm, we can use the encryption exponent e to compute the decryption exponent d and we can view the plaintext for any ciphertext. In reverse, if I know n, d, and e, how can I efficiently factor n? I got up to the step where I have $k=ed-1$ but then how can I find p and q? In fact, I don't even have $\phi (n)$ . I just know k, which is one of its multiple. Thanks! 174.29.105.219 (talk) 02:12, 14 April 2010 (UTC)[reply]

If ed-1 is significantly smaller than n, you can factor ed-1 to get prospects for p-1 and q-1 using a smaller search space than you would factoring n itself. Then, with the small number of prospects for p-1 and q-1, you just add one to each of them and see if it evenly divides n. -- kainaw ™ 02:26, 14 April 2010 (UTC)[reply]

You can write

\phi (n)=(p-1)(q-1)=n+1-(p+q)

p and q are of order sqrt(n), so you can easily extract which multiple of phi(n) you have. Thus phi(n) follows from that and thus also p + q, and from that p and q themselves as the product of p and q is known to be n. Count Iblis (talk) 02:32, 14 April 2010 (UTC)[reply]

The multiple of phi(n) that I have ed-1 is actually much larger than n itself so there is no hope of trying to factor it. It would have been faster to probably just factor n itself to begin with. Also, how can I extract which multiple of phi(n) do I have? 174.29.105.219 (talk) 05:24, 14 April 2010 (UTC)[reply]

Suppose that n is number of many hudreds of digits, then p and q being of order sqrt(n), are many orders of magnitude less than n, so ed-1 divided by n is almost equal to that integer you seek. If you divide ed-1 by that integer you get phi(n) and once you have phi(n), you only have to solve a quadratic equation to extact p and q. Count Iblis (talk) 14:26, 14 April 2010 (UTC)[reply]

ed − 1 is not divisible by n, and it can be almost as large as n². Which integer do you want it to be divided by, again?—Emil J. 14:37, 14 April 2010 (UTC)[reply]

Oh, I see: you approximately divide ed − 1 by n, and you try integers "nearby" the result to find one of them which divides ed − 1. What is "nearby"? Well, p and q are of order √n, hence φ(n) = n(1 + O(1/√n)). ed − 1 will be of order O(n²), hence (ed − 1)/n will be of order O(n), and it will differ from (ed − 1)/φ(n) by something of order O(n/√n) = O(√n). In other words, the search space for the divisor of ed − 1 is about as large as the search space for factoring n by trial division, unless you are lucky and ed − 1 is much smaller than usual.—Emil J. 15:34, 14 April 2010 (UTC)[reply]

OTOH, I gather from our RSA page that some practical implementations apparently fix e to be as low as 3 (I can't imagine why, as any artificial restriction of the key space reduces security, but whatever). If this is the case, then ed − 1 is O(n), and Count Iblis' method works like charm. As a matter of fact, if e = 3, and p, q are large enough (read: not equal to 3), then the condition of e being coprime to φ(n) implies that p and q are both congruent to 2 modulo 3, hence φ(n) is 1 mod 3. It follows that d = (2φ(n) + 1)/3 and ed − 1 = 2φ(n), so one does not even have to perform the division, we already know the result. However, the OP's statement that ed − 1 is much larger than n suggests that their e is not that small.—Emil J. 12:36, 15 April 2010 (UTC)[reply]

ed-1 is not necessarily hard to factor, despite its size, as it may have many relatively small prime factors. Once you have factorised ed-1, create a list of its divisors, then for each pair of divisors a, b test (a+1)(b+1) to see if it is equal to n. As phi is a divisor of ed-1 then so are p-1 and q-1, so you recover p=a+1 and q=b+1. Tedious to do by hand, but fairly simple for a computerised search. And even if you can only partly factorise ed-1, you might get lucky. Gandalf61 (talk) 10:13, 14 April 2010 (UTC)[reply]

ed-1 is not necessarily hard to factor, but there is no guarantee that it isn't. Miller has described a polynomial-time algorithm for factoring n using any nonzero polynomial-sized multiple of φ(n) assuming the generalized Riemann hypothesis, which assumption can be removed at the expense of making the algorithm randomized using an idea of Rabin. The unconditional randomized polynomial-time version of the algorithm goes similar to Miller–Rabin primality test#Algorithm and running time, except that the given multiple m of φ(n) is used in place of n − 1. Once the algorithm identifies a compositeness witness a, we know that one of the following two things happens: (1)

b:=a^{d2^{r}}\not \equiv \pm 1{\pmod {n}}

but

b^{2}\equiv 1{\pmod {n}}

for some r < s, which implies that gcd(b ± 1,n) is a nontrivial factor of n; (2)

a^{m}=a^{d2^{s}}\not \equiv 1{\pmod {n}}

, which implies that gcd(a,n) is a nontrivial factor of n.—Emil J. 12:10, 14 April 2010 (UTC)[reply]

Yes, I see. And as our RSA article suggests that p and q should be chosen so that p-1 and q-1 both have at least one large prime factor, this would make factoring ed-1 especially difficult. So does this mean that if p and q are chosen appropriately, knowing both public and private keys does not make it any easier to find p, q or phi than if we just know n (although, as we can now decrypt any message, this may only be of theoretical interest) ? Gandalf61 (talk) 08:48, 15 April 2010 (UTC)[reply]

?? I just described an efficient algorithm how to find p and q given the pair of keys.—Emil J. 11:41, 15 April 2010 (UTC)[reply]

Maybe it's worth clarification that the condition on p − 1 and q − 1 having a large prime factor is imposed so that one cannot too easily factorize n without knowing the private key (and thus to break the cipher), using factoring algorithms such as Pollard's p − 1 algorithm.—Emil J. 13:22, 15 April 2010 (UTC)[reply]

As EmilJ explained, if ed -1 is of order n^2 (or even just of order n^(3/2)) then you won't be able to find p and q easily. However, it is not clear to me why that should be the case. If I design the RSA code, I pick p and q and take some e. Then I compute d using the p and q that are known to me. Why would I choose the d that only I will be using to decript messages such that e d - 1 will be a huge multiple of phi(n)? Count Iblis (talk) 14:54, 15 April 2010 (UTC)[reply]

First, for the third time: you will be able to find p and q easily in any case, you just have to use the right algorithm. Second, you don't get to choose d, it is uniquely determined by e (or rather, if you want to choose d, you can't also choose e, you have to compute it from d).

Now: why would you choose either of them such that ed − 1 will be a huge multiple of φ(n)? Because the size of ed − 1 is completely irrelevant, this number is not used in any way in either the encryption or decryption process. On the other hand, what is relevant is that as in any other encryption scheme, the cipher can be only as strong as the keys being used. If you restrict the set of keys you are choosing from, or if you select parts of the key in a predictable way, you are giving the adversary an advantage which they may exploit to break the encryption more easily. In this case it may not be entirely obvious how could the adversary benefit from having a small e when e is publicly known anyway, so here are some suggestions: (1) The adversary may be trying to break the cipher by some kind of an algorithm which uses precomputed tables; it's much easier for them to arrange this if they know beforehand that a large fraction of the key space will not be used at all. (2) If e is fixed to a specific value like 3 above, it may turn out that there are more efficient algorithms for breaking these particular instances of the cipher that do not apply to the general case.—Emil J. 16:14, 15 April 2010 (UTC)[reply]

Sum

how i can calculate Rumman sum —Preceding unsigned comment added by Abdullmajeed (talk • contribs) 06:31, 14 April 2010 (UTC)[reply]

Surely you mean Riemann sum. Staecker (talk) 19:17, 14 April 2010 (UTC)[reply]

April 15

roots of an equation

How many roots does the equation $z^{3}+{\bar {z}}=0$ have?. I guess I could plug in x+iy in place of z, seperate the real and imaginary parts and find out a simultaneous solution but is there a quicker way? Thanks.-Shahab (talk) 05:11, 15 April 2010 (UTC)[reply]

Transform the equation to the form

z^{3}=-{\bar {z}}

, then try substituting

{\bar {z}}=|z|e^{arg(z)\,i}

and consequently

z=|z|e^{-arg(z)\,i}

. --CiaPan (talk) 06:04, 15 April 2010 (UTC)[reply]

It should be clear that any root necessarily has |z| = 1 or |z| = 0. So z = 0 is a root and for |z| = 1 you can multiply through by z to get

z^{4}+|z|^{2}=0

which means z satisfies

z^{4}+1=0

and then you can find the roots of that. Rckrone (talk) 07:52, 15 April 2010 (UTC)[reply]

Notation

Suppose you are given two functions $f(x)$ and $g(x)$

Given the equation $f(x)=g(x)$ , what is the correct notation for rearranging that equation to express $x$ in terms of $f$ and $g$ ?

$x=...$ (something containing $f$ and $g$ )

--Alphador (talk) 07:02, 15 April 2010 (UTC)[reply]

{x : f(x)=g(x)} is the set of solutions to the equation. x = (f−g)⁻¹(0) is the supposed unique solution. Bo Jacoby (talk) 07:41, 15 April 2010 (UTC).[reply]

How about, where

f(x)=g(x)=y\,\!

, then

x=f^{-1}(y)=g^{-1}(y)\,\!

. ~Kaimbridge~ (talk) 15:54, 15 April 2010 (UTC)[reply]

nature makes its move

The article probability space says:

Once the probability space is established, it is assumed that “nature” makes its move and selects a single outcome, ω, from the sample space Ω. Then we say that all events from

\scriptstyle {\mathcal {F}}

containing the selected outcome ω (recall that each event is a subset of Ω) “have occurred”. The selection performed by nature is done in such a way that if we were to repeat the experiment an infinite number of times, the relative frequencies of occurrence of each of the events would have coincided with the probabilities prescribed by the function P.

What the heck is that supposed to mean? Is there a more formal description of what happens here? For example, if I repeatedly flip an unbiased coin (infinite Bernoulli process) and "nature" selects the sequence H,T,H,T,H,T... then the frequencies of occurrence coincide with the expected 50% heads, but I wouldn't call it random. Note, I also brought this up on the article talk page. I am basically asking what it means to "observe" a random variable. Thanks. 66.127.52.47 (talk) 08:42, 15 April 2010 (UTC)[reply]

Good question! Probabilities describe unknown or undetermined situations. The result of flipping a coin is unknown until the coin is flipped - then the result is known. Strictly speaking the word 'random' applies not to the result but rather to the situation. Flipping a coin six times, the outcome HTHTHT is not more probable than TTTTTT. Every outcome is unique and no outcome is random! But classifying the possible outcomes according to the number of tails gives different odds to different classes. There is one way to obtain 6 tails, (namely TTTTTT). There are 6 ways to obtain 5 tails, (namely TTTTTH, TTTTHT, TTTHTT, TTHTTT, THTTTT, and HTTTTT). There are 15 ways to obtain 4 tails, (namely TTTTHH, TTTHTH, TTTHHT, TTHTTH, TTHTHT, TTHHTT, THTTTH, THTTHT, THTHTT, THHTTT, HTTTTH, HTTTHT, HTTHTT, HTHTTT, and HHTTTT). There are 20 ways to obtain 3 tails, (namely TTTHHH, TTHTHH, TTHHTH, TTHHHT, THTTHH, THTHTH, THTHHT, THHTTH, THHTHT, THHHTT, HTTTHH, HTTHTH, HTTHHT, HTHTTH, HTHTHT, HTHHTT, HHTTTH, HHTTHT, HHTHTT, and HHHTTT). There are 15 ways to obtain 2 tails, there are 6 ways to obtain 1 tail, and there is only one way to obtain no tails (namely HHHHHH). The total number of outcomes is 64, and the odds for the 7 classes are as 1:6:15:20:15:6:1. Each outcome defines a class. The classes are called events. The idea of a probability space focus on events rather than on outcomes. I hope this helps. Bo Jacoby (talk) 09:50, 15 April 2010 (UTC).[reply]

Thanks for replying, sorry the question wasn't clear. I only meant HTHTHT as the first 6 flips of an infinite sequence that kept strictly alternating between H and T, i.e. a trivial deterministic sequence that still met the defininition, that if you repeat the experiment an infinite number of times, you get 50% probability of H and 50% T. I guess in the case of the Bernoulli process, we can say we're definining an infinite family of random variables r1,r2... so that any finite collection of them have a certain joint probability distribution, and then define a sequence with that property as "iid" (rather than going the other way, starting from a vaguely defined term and calculating the joint distribution). But I don't know what happens when the sample space is more complicated. I'm trying to understand the formalism of probability in terms of sigma-algebras and so forth, not really about flipping coins. But I'm stuck at the part where you actually draw a sample from a distribution and observe it, and how that concept is formalized. 66.127.52.47 (talk) 10:22, 15 April 2010 (UTC)[reply]

If the probability space is finite, (as is the case when flipping a coin 6 times), any subset can be regarded an event having a probability, but if the probability space is infinite, (as is the case when flipping a coin an infinite number of times), individual outcomes (such as your THTHTH...) are not necessarily events. To deal with this complication one must define which subsets are events. The answer is that the set of events must constitute a sigma-algebra. Bo Jacoby (talk) 11:39, 15 April 2010 (UTC).[reply]

Thanks, that's a good point about a single outcome not being an event on the infinite process, but I'm still not doing a good job explaining what my question is trying to get at. Consider the following proposition:

Let U be the uniform probability distribution on the interval [0,1]. Then for any pair of samples x,y drawn from U, we have x+y≤2.

This proposition is obviously true, but I would like to formally prove it as a theorem starting from the definitions of random variables, probability spaces, etc. (and likewise for similar statements). In order to do that, I'm trying to find out how axiomatic probability theory describes the process of drawing a sample from a distribution and inspecting its value. But the closest thing I can find is this thing about "nature making its move", which doesn't sound like a mathematical statement at all. How does "nature" pick ω from Ω, when Ω can be some messy uncountable set? What does it mean to "repeat the experiment" even once, and expect to get a different outcome? I'm still not sure if I'm asking something sensible. 66.127.52.47 (talk) 18:04, 15 April 2010 (UTC)[reply]

The Earth Ellipsoid

How many points on the Earth need to be precisely defined so as to uniquely define the Ellipsoid of the Earth. —Preceding unsigned comment added by 116.90.224.116 (talk) 10:41, 15 April 2010 (UTC)[reply]

An Earth ellipsoid reference frame model is an oblate spheroid defined by two parameters: its equatorial axis and its polar axis. Adding in three degrees of freedom for the co-ordinates of the centre of the spheroid and two more for the direction of its polar axis, we have seven degrees of freedom altogether. Assuming you can measure the Cartesian co-ordinates of one point relative to another with any required degree of accuracy, then measuring the relative co-ordinates of any seven points in general position on the ellipsoid should give you enough data to uniquely define the ellipsoid ("in general position" means that you do not use points that are in some special relationship to one another, such as seven points all on the equator).

However, note that the Earth ellipsoid is a model, respresenting a standard datum. If you picked seven actual points on the Earth's surface, you could define an ellipsoid that passed exactly through those points - but at other places it would not be a good approximation to the Earth's surface. Earth ellipsoids are usually defined so as to resemble an "average" shape of the Earth in some sense, rather than to pass through any specific points. The more actual points you measure, the closer you can make your datum to resemble the "average". Gandalf61 (talk) 12:06, 15 April 2010 (UTC)[reply]

Excellent answer,Thanks a lot. —Preceding unsigned comment added by Amrahs (talk • contribs) 15:31, 15 April 2010 (UTC)[reply]

The answer is nine. If you have a given ellipsoid and you mark nine points on it then the given ellipsoid is the only one that can contain the nine marked points. Let me explain:

An ellipsoid is an example of a quadric. A general quadric in $xyz$ -space has the equation

a_{1}x^{2}+a_{2}y^{2}+a_{3}z^{2}+a_{4}xy+a_{5}xz+a_{6}yz+a_{7}x+a_{8}y+a_{9}z+a_{10}=0,\,

where each of the $a_{i}$ are real numbers. Thus, for every a ∈ ℝ¹⁰ we get a quadric surface. However, different points of ℝ¹⁰ give the same quadric. We see that a ∈ ℝ¹⁰ and λa ∈ ℝ¹⁰ give the same quadric for any real number λ ≠ 0:

(\lambda a_{1})x^{2}+(\lambda a_{2})y^{2}+(\lambda a_{3})z^{2}+(\lambda a_{4})xy+(\lambda a_{5})xz+(\lambda a_{6})yz+(\lambda a_{7})x+(\lambda a_{8})y+(\lambda a_{9})z+(\lambda a_{10})=0\,

\iff \lambda (a_{1}x^{2}+a_{2}y^{2}+a_{3}z^{2}+a_{4}xy+a_{5}xz+a_{6}yz+a_{7}x+a_{8}y+a_{9}z+a_{10})=0.\,

\iff a_{1}x^{2}+a_{2}y^{2}+a_{3}z^{2}+a_{4}xy+a_{5}xz+a_{6}yz+a_{7}x+a_{8}y+a_{9}z+a_{10}=0.\,

What this means is that the space of quadrics is given by the quotient space ℝ¹⁰/~ where a ~ b if and only if there exists λ ≠ 0 such that a = λb. This quotient space is denoted by ℝℙ⁹, its elements are given in homogeneous coordinates and are of the form (a₁:a₂: … :a₁₀) ∈ ℝℙ⁹. The symbol ℙ is used to denote the projective space. The bottom line here is that ℝℙ⁹ is locally a nine-dimensional manifold. So the space of quadrics has nine degrees of freedom. There are some genericity conditions to worry about in the abstract setting. But in the case of ellipsoids − which are generic quadrics − we need to specify nine points to uniquely define an ellipsoid. So if you have a given ellipsoid and you mark nine points on it then the given ellipsoid is the only one that can contain the nine marked points.

Regarding the genericity conditions. You could have a sphere, which is an example of an ellipsoid, and you could mark your nine points on the equator. Then the only ellipsoid that contains those points would by your sphere. However, the plane (an example of a degenerate, i.e. non-generic, quadric) that contains the equator would also contain these nine points. So the genericity conditions apply to your choice of points. Choosing points on the equator is highly non-generic because they are co-linear. If you perturb any point slightly then you will almost always have nine non-co-linear points. So to satisfy the genericity conditions you need to choose nine points in general position. •• Fly by Night (talk) 15:35, 15 April 2010 (UTC)[reply]

Yes, a general scalene elipsoid has nine degrees of freedom, but an Earth ellipsoid is not a scalene ellipsoid, it is an oblate spheroid - it has rotational symmetry about its polar axis - so it only has seven degrees of freedom. Gandalf61 (talk) 09:54, 16 April 2010 (UTC)[reply]

The earth is approximately spherical. Ellipsoidal is an even closer approximation. The actual shape of the equipotential surface is called the geoid and it is not quite ellipsoidal, because of the unequal distribution of mass of the continents, etc. And even more accurately than the equipotential surface, you really have to describe every single point, to account for every rock, hill, bump on the ground, etc. 66.127.52.47 (talk) 17:41, 15 April 2010 (UTC)[reply]

How does counting degrees of freedom automatically translate into the number of points necessary to define a surface? Doesn't a general line in 3-space have three degrees of freedom? But isn't such a line is uniquely defined by only two points? 124.157.234.136 (talk) 15:11, 16 April 2010 (UTC)[reply]

Price elasticity , quantity demanded

If the percentagechange in the quantity demanded is equal to the percentage change in the price that cuased the change in the quantity demanded, the elasticity coufficient will be equal to one? —Preceding unsigned comment added by Elista (talk • contribs) 13:07, 15 April 2010 (UTC)[reply]

The instantaneous price elasticity demand coefficient will be negative one, assuming that you meant "increasing the sales price will decrease the sales unit volume by the same percentage". Of course, this only works for small percentage changes, since it would mean increasing price by 100% (doubling the price) would decrease sales unit volume by 100% (so no sales at all). That seems rather odd, so this isn't the best way to represent price elasticity over large changes in price. Since the price-demand curve is nonlinear, the relationship isn't a direct one, but rather one described by a formula. Calculus may be used to derive this formula. StuRat (talk) 16:01, 15 April 2010 (UTC)[reply]

What an amazingly well-written article that is. Maybe we should club together and buy the poor guy that wrote (most of) it a car, or something. Elista, as the article notes, in many real world circumstances positive coefficients are used for ease, so +1 may be the "correct" answer in your context. And yeah, StuRat, you're unlike to have a PED of (-)1 for such an operation. - Jarry1250 ^{[Humorous? Discuss.]} 13:11, 16 April 2010 (UTC)[reply]

April 16

Internet searches for non-linear notations

Please see Wikipedia:Reference desk/Computing#Internet searches for non-linear notations. -- Wavelength (talk) 01:20, 16 April 2010 (UTC)[reply]

Why don't AND and OR form a ring?

From Exclusive or#Relation to modern algebra:

The systems

(\{T,F\},\wedge )

and

(\{T,F\},\lor )

are monoids. This unfortunately prevents the combination of these two systems into larger structures, such as a mathematical ring.

What property of a ring does $(\{T,F\},\lor ,\wedge )$ not satisfy? Neon Merlin 01:40, 16 April 2010 (UTC)[reply]

There's no additive inverse (no matter which of the operations you want to call addition). However, see Boolean ring, which is "morally" the same thing, and is a ring. --Trovatore (talk) 01:43, 16 April 2010 (UTC)[reply]

Markov Chains

At the top of the article Markov chain, it reads "This article may be too technical for most readers to understand"
AND IT IS! :P
Consider three states, i j and k.
$p_{ij}=a$
$p_{ik}=b$
$p_{ii}=1-(a+b)$
$p_{jk}=c$
$p_{ji}=d$
$p_{jj}=1-(c+d)$
$p_{ki}=f$
$p_{kj}=g$
$p_{kk}=1-(f+g)$

How does one work out the probability, assuming the current state is 'i', that the state in n time steps will be x (i, j, or k).
ps I have zero experience with Markov Chains.--203.22.23.9 (talk) 03:07, 16 April 2010 (UTC)[reply]

First you write the transition probabilities as a matrix where the

(m,n)

entry is the probability to move from state m to n (I'll rename i, j and k as states 1, 2 and 3):

P={\begin{bmatrix}1-a-b&a&b\\d&1-c-d&c\\f&g&1-f-g\end{bmatrix}}

Then calculate the matrix power

P^{n}\;\!

. This represents the probability of transition between states in n steps. So, for example, the (1, 2) entry of

P^{n}

is the probability that in n steps you will be in state 2, given that you are currently in state 1. -- Meni Rosenfeld (talk) 05:33, 16 April 2010 (UTC)[reply]

what's the most useful theorem a computer programmer should know exists/is true?

i'll throw one out there. it is helpful if you know how to do boolean algebra, you can simplify long statements and thereby complexity. now you: are there still more useful theorems?

Number generation based on past data

I am trying to generate a "random number" that is based on past data. For instance, based on past rainfall, I am trying to generate simulationed numbers for future years. I am not sure what sort of model I should use for this(my statistics is very limited). D--216.96.255.184 (talk) 13:46, 16 April 2010 (UTC)oes anyone have any ideas or know of a good place to look to find this out?[reply]

I don't think there is an easy answer to this, as it depends on what assumptions you make about your data. If you assume that each year's rainfall is independent of all other years, then you are looking for a probability distribution that fits your data. A common distribution (or, more precisely, family of distributions) is the normal distribution. You can use your data to estimate the mean and standard deviation of a suitable normal distribution. There are then various normality tests which will tell you whether this distribution is a good fit to your data. If it isn't, then you can try a different type of distribution - there are plenty to choose from - but beware of the danger of overfitting. If, on the other hand, you think one year's rainfall may be influenced by rainfall in the previous year (or several years) then you may want to use a Markov chain model - or maybe somethiong even more complex than that. Gandalf61 (talk) 15:14, 16 April 2010 (UTC)[reply]

Probability perception

Not quite perfect for this desk, but a human side to mathematics: how many heads have to be flipped continuously before the average person believes the coin is fixed? For example, if I flipped HHHHHHHH, I'd think that was fixed (the "probability" being 1/256); HH, on the other hand, and I wouldn't think so. I've tried researching this for a bit, but the wide choice of words isn't ideal. Of course, the setting makes a difference, but any data would be great. - Jarry1250 ^{[Humorous? Discuss.]} 16:03, 16 April 2010 (UTC)[reply]

We have an article, Checking whether a coin is fair. Does it help? Note if the person suspects ahead of time that the coin is biased, ambiguity aversion may cause people to overestimate the probability. 66.127.52.47 (talk) 17:37, 16 April 2010 (UTC)[reply]