0
$\begingroup$

Imagine you have some computer program that requires an input of N values (say $a,b,c$), and calculates some homogeneous polynomial (with some small natural number coefficients) returning an integer number as a result. Is there any way of determining such a polynomial with a clever choice of $a,b,c$?

Edit: for argument's sake, say the polynomial has the same or fewer terms than the number of indeterminants + 1, so we aren't getting into the "not enough information" territory.


Background Information

I've been working on a computer program that performs non-trivial operations on a data structure. Each entity in this data structure adopts a value from a provided set of values (such as $a,b,c$), and the result of the program is another data structure with values $p(a,b,c)$, where $$p(X,Y,Z) = \sum_{A,B,C} \beta_{A,B,C} X^AY^BZ^C$$$$A,B,C \in \mathbb{N}\qquad A+B+C = N$$$$\beta_{A,B,C} \in \mathbb{N},\qquad \beta_{A,B,C} < M$$ for some known $N$ and some coefficient maximum bound $M$ (e.g. I can guess that all $\beta$ are less than $20$ for some situations).

A small side-project is taking off, where it'd be useful to actually know the coefficients in these polynomials. I could write a new version of the program, but as this is a small side-project, I'd rather not. Instead, I would like to provide a value to $a, b$ and $c$ and determine $p(X,Y,Z)$ from the output. I'd like to avoid running the program multiple times to find $p$, if possible.


Ideas

The first obvious place to look is prime numbers. If I choose, say, $967, 971, 977$ then a monomial should be easy to determine by prime factorisation, such as long as its coefficient is less than $967$. However, in a polynomial things get more complicated. Can the addition of the monomials produce a non-unique decomposition? Even if we know that they're all of the same degree?

I'm a physicist so my mathematical background doesn't contain a lot of pure mathematics - so it may very well be a well-known problem, but my searching so far has been in vein.

$\endgroup$
0
$\begingroup$

I'm now pretty sure that it isn't possible.

Given a number $D$ of indeterminates, the number of terms in a homogeneous polynomial of degree $N$ is always greater than $D$ for $N > 1$. For the monomial case, the knowledge that it is a monomial caps the number of terms to 1.

For example, consider a polynomial of degree 2 in 3 indeterminates ($a,b,c$) - the terms are factors of ($a^2, b^2, c^2, ab, ac, bc$); I hadn't taken into account that a coefficient of 0 is still something that needs to be determined. This is one of the simpler examples of what I'm looking at, so it looks like I'll be refactoring the codebase to handle symbolic entities.

$\endgroup$
0
$\begingroup$

First of all, let's use $x, y, z$... for variables (that's what they are usually called, the word "indeterminate" sounds like something that Newton could have used in 17th century math text) and $a, b, c$... for coefficients.

In a general form that is clearly impossible even if you know that the polynomial is as simple as $ax+by+cz$ (degree 1). Simply put, if you know just the value of $ax+by+cz$ you cannot determine $a$, $b$ and $c$ even if $x$, $y$ and $z$ were chosen in a "clever" way. However, if you know that the coefficients are, say, non-negative integers less than 10 (those guys are also sometimes called digits :) ) then of course by submitting $x=1$, $y=10$ and $x=100$ you will be able to determine $a$, $b$ and $c$ by the answer $S=ax+by+cz$ (they will simply be the digits of $S$ in its decimal representation). Same goes for any upper bound of $n$ -- you would use 1, $n$ and $n^2$.

Similar thing can be done for any higher degree but the numbers you'd have to submit as variables will have to be very large -- not sure if that will help you in a real-life situation. For instance, let us say we know that $$ P(x,y,z) = ax^2+by^2+cz^2+dxy+exz+fyz $$ and we want to find values of coefficients $a$, $b$, $c$, $d$, $e$ and $f$ from just one value of that polynomial. Again, generally you cannot do that but if you know that all coefficients are less than some natural number $n$ you could choose $x=1$, $y=n$ and $z=n^3$. (1, $n$ and $n^2$ will not work because you will get $a+dn+(b+e)n^2+fn^3+cn^4$ and that will not solve the problem). Once again, coefficients will be digits of $P(x,y,z)$ in $n$-base number system.

Generally you will need powers of $n$ with the set of non-negative integer degrees $a_1$, ...$a_m$ such that no sum of $k$ numbers ($k$ here plays the role of our polynomial's degree) from that set would repeat. So when $k=2$ then powers $(a_1=0,a_2=1,a_3=2)$ will not work since $a_2+a_2 = 1+1=0+2 = a_1+a_3$, but $(0,1,3)$ will work (no repetitions!).

$\endgroup$
  • $\begingroup$ That leads to an interesting and well-known problem (I think it is, but I am not a number theory specialist): For fixed natural numbers $p$ and $q$ what is the "minimum" set of $p$ non-negative integers such that no sums of $q$ of these numbers (using same number multiple times is allowed) repeat? By "minimum" here I mean the set with the minimum possible maximum element. $\endgroup$ – JimT Feb 6 '17 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.