Primes and Polynomials

[JimBob81345]

Does there exist a polynomial P(x) with rational coefficients such that for every composite number x, P(x) takes an integer value and for every prime number x, P(x) does not take on an integer value?

Can someone please guide me in the right direction? I've tried to consider the roots of the polynomial and its relation with the input but without luck.

 

[mfb]

Assume there is such a polynomial of degree n. Then there is also one where P(x)=0 for the first n primes. This fully determines the polynomial up to a constant - and I don’t see how this constant could be chosen to work.

Edit: Wait, I reversed the integer and non integer value, but the argument works for both.

 

[Mark44]

Does there exist a polynomial P(x) with rational coefficients such that for every composite number x, P(x) takes an integer value and for every prime number x, P(x) does not take on an integer value?

Is this what you mean?
... for every composite number x, P(x) is an integer, and for every prime number x, P(x) is not an integer?

Your wording of "takes an integer value" and "does not take on an integer value" was confusing to me.

 

[JimBob81345]

Assume there is such a polynomial of degree n. Then there is also one where P(x)=0 for the first n primes. This fully determines the polynomial up to a constant - and I don’t see how this constant could be chosen to work.

Edit: Wait, I reversed the integer and non integer value, but the argument works for both.

I am confused by what you are saying. If there exists a polynomial of degree n then yes there also exists a polynomial with the roots being the first n primes. But how does this determine the polynomial to be a constant?

 

[JimBob81345]

A positive integer is part of the set A if the digits in its decimal representation form a non-decreasing sequence from left to right. For example, 149 and 1223 are both in A but 745 is not. Does there exist a polynomial P(x) with rational coefficients such that if x is a number in A, then P(x) is an integer and if x is not a number in A, P(x) is not an integer?

My Observations:
- If this polynomial exists then there exists an infinite number of polynomials which satisfy the above condition.
- The roots of P(x) are number for which it equals 0 (an integer), thus, its roots (if the are positive integers) must be of the set A.
-

Should I research the properties of numbers in the set A before further attempting this problem?

 

[Mark44]

This fully determines the polynomial up to a constant

But how does this determine the polynomial to be a constant?

@mfb didn't say that the polynomial was a constant -- he said "up to a constant." For example, the quadratic polynomial y = a(x - 1)(x - 2) has 1 and 2 as its roots, independent of the value of a.

 

[mfb]

@mfb didn't say that the polynomial was a constant -- he said "up to a constant." For example, the quadratic polynomial y = a(x - 1)(x - 2) has 1 and 2 as its roots, independent of the value of a.

Or, more explicitly: Every polynomial of degree 2 with these roots can be expressed as a(x-1)(x-2).

Edit: I merged the other thread into this one as the problem is very similar. See post #5.

 

[JimBob81345]

I still don't understand, can you be a little more detailed?

 

[mfb]

Here is an example.
Let's try find a polynomial function of degree 2 (a parabola) that has integer values exactly at x=1, 2 and 3. Assume there is such a function f(x).
We can find a linear function g(x) such that g(1)=f(1) and g(2)=f(2), namely g(x)=(f(2)-f(1))x + 2f(1)-f(2). Note that both coefficients are integers [note*], and g(x) is an integer for every integer x.

If f(x) has the properties we want, then h(x)=f(x)-g(x) has it as well, because we are only subtracting integers. We also know h(1)=h(2)=0. Every parabola with the last property can be expressed as h(x)=a(x-1)(x-2) for some a.

Let's plug in x=3: h(3)=2a. We want this to be an integer. That is possible, of course, but what happens if we look at other values? h(4)=6a. No matter which a we choose, if 2a is an integer, then 6a=3*2a will be an integer as well. This contradicts our requirement that our function has integer values only for 1,2,3.

I used three specific points here (1,2,3), but you can generalize this to any three points, e.g. 1,4,6 or 2,3,5. Similarly, you can ask for a polynomial function of degree 3 that has integer values only at 1,4,6,8 or 2,3,5,7 (see above: It doesn't matter if you take the set of primes or the set of non-primes).
I picked the degree first here, but that doesn't matter. If there is a polynomial function that has integer values only at prime numbers, then it has some degree n, and we can look at the first n non-prime numbers (or prime numbers) to determine the polynomial up to a constant (the "a" from above). While you have some choice in the constant, I can't see how any choice would lead to the correct result for every number. This is not a strict mathematical proof, but I'm quite confident that there is no such polynomial function.

*note: this doesn't generalize that nicely, but the coefficients stay rational with small denominators, and g(x) keeps getting integer values elsewhere

 

[JimBob81345]

Thank you for the clarification. I have a related problem:
Suppose a Polynomial P(x) (with rational coefficients) exists such that for every input that is prime, P(x) outputs an integer. Does P(x) have to output an integer for every integer inputted or can you input some non-prime integer in P(x) so that the output is not prime?

In other words
Prime --> P(x) --> Integer
Is it possible for the following to happen? (Even for one number)
Non-prime --> P(x) --> Non-integer

 

[mfb]

That is a weaker problem than the original one.

1/9 (x-1)²(x-2)²(x-3) is zero for x=1, 2 and 3, it is an integer if x has remainder 1 or 2 when divided by 3 (which applies to all primes apart from 3), and it is not an integer for x=6 (where it is 400/3), x=9, x=12, and all other multiples of three that don't follow the pattern 9n+3.

That makes a nice math puzzle.

Edit, easier:

1/4 (x-1)²(x-2) is zero for x=1 and x=2, an integer for all odd x and not an integer for x=4n for all integers n.

 

[JimBob81345]

A positive integer is part of the set A if the digits in its decimal representation form a non-decreasing sequence from left to right. For example, 149 and 1223 are both in A but 745 is not. Suppose a polynomial P(x) exists so that it outputs an integer for every input which is in the set A. Does P(x) have to output an integer for every integer inputted?

Let me try this by myself:
I think the answer is yes.
Assume that such a polynomial exists, f(x). Now say another linear function g(x) with integral coefficients exists so that f(11) = g(11) and f(12) = g(12) (11 and 12 are the smallest numbers in the set A.) Let's say now we let h(x) = f(x) - g(x). h(x) has the same properties as f(x) since we are just subtracting integers. We know that h(11) = h(12) = 0. So h(x) = a(x-11)(x-12). For x=13, h(x) = 2a which we want to be an integer. However, if we plug in x=21 we get h(21) = 90a which will be an integer if 2a is an integer. We can repeat this for every integer not in A. Thus such a polynomial cannot exist.

 

[mfb]

Your argument only rules out parabolas, not polynomials of any degree.

 

[JimBob81345]

How would you prove it for polynomials of any degree?

 

[mfb]

Instead of degree 2, assume degree n and verify that all the steps can be generalized.

 

[JimBob81345]

Does g(x) have to be a linear function?

 

[mfb]

In general it cannot be a linear function. You need a polynomial of grade n-1 to get n roots of f(x)-g(x) at the places where you want them.

 

[JimBob81345]

I have h(x) = a(x-y_1)(x-y_2)...(x-y_n) where y_k is the k-th number in the set A. I can't seem to progress further.

edit: fixed

 

[mfb]

The prefactor is missing.

The last step is probably difficult if you want to prove it properly.

 

[JimBob81345]

How do you suggest I approach it? It doesn't seem to be possible using the method you proved the degree 2 case

 

[mfb]

It is your problem, I think you should contribute something as well. Finding the right approach is the interesting part of mathematics.

It could help to look at other easier cases first, e.g. third degree polynomials.

 

[JimBob81345]

I think I should use a different approach than the one used previously.

 

[JimBob81345]

mfb, I believe I got it. Can you please check over this solution?
for deg(h) = 1, we have h(x) = k(x-11) which gives k for h(12) (k must be an integer). Since x-11 is an integer for all integer x, k(x-11) must be divisible by k, thus, k(x-11) must be an integer.
let y_i denote the i-th number in A.
Assume h(x) is an integer for some x=k.
This is what we want to prove. If k(x-11)(x-12)...(x-y_i) is an integer, then k(x-11)(x-12)...(x-y_i)(x-y_(i+1)) is an integer. (proof by indiction).
(x-y_(i+1)) is an integer because x and y_(i+1) are integers, and if you multiply an integer by an integer you get an integer. So our proof is done for all cases.

 

[mfb]

Assume h(x) is an integer for some x=k.

You set x=k?

This is what we want to prove. If k(x-11)(x-12)...(x-y_i) is an integer, then k(x-11)(x-12)...(x-y_i)(x-y_(i+1)) is an integer. (proof by indiction).

The k might change depending on i. Induction might work, but it needs more thought to make a solid proof.

There is another thing that I didn't prove properly - I'm highly confident it is true, but a proof would be better: Show that g(x) is always an integer for all integer x. This is clear if f is a parabola, and it is easy to prove if we take n subsequent integers where h(x) is zero, but the general case needs some more thought.

Where does the problem come from?

 

[JimBob81345]

Sorry x is not equal to k
I am delving into research mathematics and this is a problem I proposed to myself

 

[JimBob81345]

Can a be an irrational number in f(x) = a(x-11)(x-12)...(x-y_n)?

 

[mfb]

That would make the function irrational at all integers (at all rational numbers, even) where it is not zero.