1
$\begingroup$

Let $f(x)$ be any continuous, differentiable function that has extrema and that $f(x) \geq 0$ for all $x$ and has a finite amount of roots (it is not always a polynomial). Let $g(x)$ be a function (written in terms of $f(x)$) that flips sign only when a root of $f(x)$ is encountered. For example, let's say that $f(x)$ has roots at $2,3,7,11$. That means if from $0$ to $2$, $g(x)$ is positive, from $2$ to $3$, $g(x)$ should be negative. From $3$ to $7$ it should be positive and from $7$ to $11$ it should be negative. $g(x)$ should be written in terms of $f(x)$; therefore $g(x)$ should be a general equation. You should not need to know the roots of $f(x)$ in order to construct $f(x)$. $g(x)$ does not have to be continuous nor differentiable. Hopefully, $g(x)$ is closed form (ie. no $\sum$ or $\prod$). What is one definition of $g(x)$? Or is such a function possible to construct?

In any answer, please use $f(x)=\sin^2(\frac{33}{x}\pi)+sin^2(x \pi)$ as the example function.

Background: I was thinking about this problem because I wanted to know if it was possible to find roots numerically for functions that are all positive and have other extrema other than the roots (so something like f(x)/f'(x) wouldn't work). Newton's, fixed point, and so on are only valuable if you start near the root, and even then, with a function like the example, it's not guaranteed to work. Bisection is the only one guaranteed to work, but I need to get the equations in a form so that can work.

EDIT: After giving it some thought, I'm thinking that such $g(x)$, if possible, will probably include sine, cosine, and/or tangent in some way, but I'm not sure how. I was hoping someone could help me.

$\endgroup$
  • 1
    $\begingroup$ Are we just finding two functions, $f(x)$ and $g(x)$? $\endgroup$ – N. Bar Aug 4 at 1:26
  • $\begingroup$ @N.Bar No, $g(x)$ is just supposed to be written in terms of $f(x)$, which is any continuous, differentiable function. $\endgroup$ – Quote Dave Aug 4 at 1:27
  • 4
    $\begingroup$ Perhaps we define "positive" differently. For me, a function $f$ is positive when $f(x) > 0$ for all $x$ in its domain. $\endgroup$ – Rylee Lyman Aug 4 at 1:44
  • 2
    $\begingroup$ Any easy way to do this would lead to a rapid algorithm for integer factorization precisely via your example function, which means that there is no (known) easy way to do this. $\endgroup$ – Micah Aug 22 at 18:40
  • 1
    $\begingroup$ I suspect the same ulterior motivation as @Micah described -- integer factoring can be easily reduced to this problem and it would be fast if the $g(x)$ we come up with is reasonably fast to evaluate numerically. This may not be the case, though: $g(x)$ might exists but be defined by a slowly converging alternating series which just creeps very close to zero and in order to determine even just its sign at some point, one would need to evaluate too many terms first. $\endgroup$ – Peter Košinár 20 hours ago
2
$\begingroup$

If your $f$ is a polynomial, here is a way to do this. Let $g(x) = \tfrac{f(x)}{\mathrm{GCD}(f(x), f'(x))}$. Note that the GCD of two polynomials can be computed by the Euclidean algorithm without factoring the polynomials.

Why this works: Since $\mathrm{GCD}(f(x), f'(x))$ divides $f$, the only zeroes of the GCD are zeroes of $f$. If $r$ is a zero of $f$ with multiplicity $m$, then $r$ is a zero of $f'(x)$ with multiplicity $m-1$, so $r$ is a zero of $\mathrm{GCD}(f(x), f'(x))$ with multiplicity $m-1$, so $r$ is a zero of $g(x)$ with multiplicity $1$. In other words, this is a way to turn $\prod (x-r_i)^{m_i}$ into $\prod (x-r_i)$, as in pre-kidney's answer.

$\endgroup$
  • $\begingroup$ This doesn't help much since my example is not a polynomial, but that is interesting. $\endgroup$ – Quote Dave 2 hours ago
2
$\begingroup$

$\require{mathtools}$Let $x_1 < x_2 < \dots < x_k$ be the roots of $f$. Write $\sigma$ for the following function:

$$\sigma(x) = \begin{cases} -1 & x \le x_1 \\ (-1)^i & x_{i-1} < x \le x_i,\; 2 \le i \le k \\ (-1)^{k+1} & x_k < x \end{cases}$$

Then $g(x) = \sigma(x)f(x)$. One way to think of $\sigma$ is as a sum of indicator functions and their negatives. I'm not sure if this is what you were looking for?

$\endgroup$
  • $\begingroup$ I believe you would need to know (or at least calculate) the roots for this to work, which is not what I want. $\endgroup$ – Quote Dave Aug 8 at 23:11
  • $\begingroup$ Any such $g$ tells you what the roots of $f$ are, so I think I'm too confused to be more help, sorry! $\endgroup$ – Rylee Lyman Aug 9 at 0:31
  • $\begingroup$ It's ok, I just wanted a function that flipped sign at every root, without having to calculate the roots themselves. $\endgroup$ – Quote Dave Aug 9 at 0:54
2
$\begingroup$

From context clues it seems like you are looking for an algorithm that can compute $g(x)$ from $f(x)$ without first having to compute the roots of $f(x)$, since that would defeat the purpose (as you would like to use $g(x)$ as a step in determining the roots of $f(x)$ numerically). I am not optimistic that you will find such an algorithm, simply for the reason that it seems no easier to find such a $g(x)$ than it is to find the roots using standard numerical techniques.

However, there are still interesting things to say here. First let me point out that in the case of a polynomial, we would necessarily have $$ f(x)=\prod_{i} (x-r_i)^{2n_i} $$ for some integers $n_i$ (up to multiplication by an overall constant), and then the most natural choice of polynomial satisfying your conditions would be $$ g(x)=\prod_{i} (x-r_i). $$ The two polynomials $f(x)$ and $g(x)$ bear the same relation as do the characteristic polynomial and the minimal polynomial of a matrix in linear algebra. There are computational approaches for computing the minimal polynomial of a matrix, which could be used in this problem: starting from the original polynomial $f(x)$, you can put the coefficients (no knowledge of the roots required!) into a so-called companion matrix (whose characteristic polynomial is automatically equal to $f(x)$) and then use the mentioned computational approach to calculate the minimal polynomial of the companion matrix, which will equal $g(x)$. (No claims for efficiency here...) This type of method could be made to apply to non-polynomials by using an approximation scheme.

To address your specific example $$ f(x)=\sin^2\left(\frac{33}{x}\pi\right)+\sin^2(x \pi), $$ let me start by pointing out the obvious, which is that $f(x)=0$ if and only if both of the two terms are equal to zero. The second term is zero precisely when $x\in\mathbb Z$, and the first term is zero precisely when $33/x\in\mathbb Z$. Thus the roots occur when $$ x=-33,-11,-3,-1,1,3,11,33. $$ If you heuristically apply a method similar to what I suggested above for polynomials, you would end up with $$ g(x)=(x^2-33^2)(x^2-11^2)(x^2-3^2)(x^2-1^2), $$ which can be compared with the expressions you get from heuristically manipulating Euler's infinite product

$\endgroup$
  • $\begingroup$ Well, is there any way to numerically find the roots of my $f(x)$ without factoring $33$? Also, how would you take my example $f(x)$ and turn it into a polynomial, say from $x=1$ to $x=33$? This "companion matrix" looks interesting. $\endgroup$ – Quote Dave 2 hours ago
0
$\begingroup$

It is impossible to write such a function $g(x)$ just in terms of $f(x)$. Suppose that the functions $f_1(x)$ and $f_2(x)$ are defined as follows:

$$f_1(x) = x^2,$$

$$f_2(x) = \begin{cases} 2x^2, & x \le -1, \\ 1 + x^4 & -1 < x < 1, \\ 2x^2 & x \ge 1. \end{cases}$$

Both functions are continuous and differentiable. On the other hand, let $g_1(x)$ and $g_2(x)$ denote the corresponding functions. Clearly $g_2(x)$ has the same sign for all $x$, but $g_1(x)$ has to change signs at $x = 0$. But since $f_1(x) = f_2(x)$ for $x \ge 1$, any possible construction of the $g_1(x)$ and $g_2(x)$ has to "know" what is happening on the interval $[-1,1]$ as an input, since it is not determined just from $f_i(x)$ in the range $x \ge 1$ given that you are only assuming it is differentiable. So it is certainly impossible to give $g(x)$ "as a function of $f(x)$" because it depends on more than $f$ at $x$ or even in a neighborhood of $x$.

New contributor
user697746 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • $\begingroup$ "$f_1(x)=f_2(x)$ for $x \geq 1$" is not true. $\endgroup$ – Leo 2 days ago

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.