What is an example of a proof by minimal counterexample?

I was reading about proof by infinite descent, and proof by minimal counterexample. My understanding of it is that we assume the existance of some smallest counterexample $A$ that disproves some proposition $P$, then go onto show that there is some smaller counterexample to this which to me seems like a mix of infinite descent and 'reverse proof by contradiction'.

My question is, how do we know that there might be some counterexample? Furthermore, are there any examples of this?

Answer

Consider, for instance, the statment

Every $n\in\mathbb{N}\setminus\{1\}$ can be written as a product of prime numbers (including the case in which there's a single prime number appearing only once).

Suppose otherwise. Then there would be a smallest $n\in\mathbb{N}\setminus\{1\}$ that would not be possible to express as a product of prime numbers. In particular, this implies that $n$ cannot be a prime number. Since $n$ is also different from $1$, it can be written as $a\times b$, where $a,b\in\{2,3,\ldots,n-1\}$. Since $n$ is the smallest counterexample, neither $a$ nor $b$ are counterexamples and therefore both of them can be written as a product of prime numbers. But then $n(=a\times b)$ can be written in such a way too.

complex numbers - Identities derived from Euler's Identity

I am just learning about Euler's identity. When messing around with it, I am getting some unsettling identities, which, I believe, is probably due to my lack of application of certain rules.

Starting with:$$e^{\pi i}=-1$$
Is this statement true:
$$\pi i = \ln(-1)$$

$$\to \ln(-1*n)= \pi i+\ln(n)$$
Also this one clearly does not hold up:
$$\ln(1)=0$$
$$\ln(1)=\ln(-1*-1)= \ln(-1)+\ln(-1)=\pi i + \pi i$$
$$\to 2\pi i=0 \to2=0$$
Please advise me on what I am missing.

Answer

Like square root, log is treated as a "multi-valued function." It's just that when we restrict to the positive real line, we can make it single-valued. (Just as we do with square root in algebra 1.)

So the first few things you derived are right: one of the logarithms of $-1$ is $\pi i$. The others all differ from it by multiples of $2\pi i$. So when you find that $\log(1) = 0$ and $\log (1) = 2\pi i$, that's fine: it just says that there are many values of the log. (Sorta like writing $1^\frac{1}{2} = 1$ and $1^{\frac{1}{2}} = -1$, which each mean that the thing on the right, squared, gives you $1$.)

To say this a bit more elegantly: there is no single log function defined on the whole complex plane (except the origin) that's continuous on the whole complex plane (except the origin), just as there's no continuous square root function defined on the whole complex plane.

By long tradition, we agree to not try to make log continuous on the negative real axis; we can then define a single consistent logarithm that's continuous everywhere except the negative real axis (and 0, where it's undefined). This single consistent log, for which $\log(1) = 0$, is called the "principal branch" of the logarithm. It's sometimes denoted $\mathrm{Log}$, I believe.

There's another perfectly good logarithm-like function, which I'll call $\widehat{\log}$: it's defined by

$$
\widehat{\log}(x) = \log x + 2 \pi i
$$

It has all the properties of $\log$ except that $\widehat{\log}(1) = 2\pi i$ instead of $0$.

You can also define other log-like things, by adding $4 \pi i$, $-6 \pi i$, etc. to $\log$.

Taken together, we get something for which
$$
\log(ab) = \log(a) + \log(b)
$$
where here "log" denotes any of the functions I mentioned above,
holds in a kind of limited sense: if you add $\log(a)$ and $\log(b)$, you'll get $\log(ab)$...but only up to multiples of $2 \pi i$. That is to say:

$$
\log(ab) - \log(a) - \log(b) = 2\pi i ~n
$$
for some integer $n$.

functional equations - Finding all continuous functions such that $f^2(x + y) − f^2(x − y) = 4f(x)f(y)$

I've been working on the following homework problem:

Find all continuous functions $f : \mathbb{R} → [0,∞)$ such that $f^2(x + y) − f^2(x − y) = 4f(x)f(y)$ for all real numbers $x, y$.

The first problem I have is I am not sure what is meant by "finding all continuous functions". Can someone show me what the ending statement should look like?

Secondly, I'm not sure what to do with the relations I've derived. The most helpful are:

$f(0) = 0$

$f(x) = f(-x)$

$f(2x) = 2f(x)$

I also know that:

$f(2) = 2f(1)$

$f(3) = \frac{3}{2}f(2)$

$f(4) = 2f(2) = 4f(1)$

This leads me to believe that $\frac{f(a)}{f(b)} = \frac{a}{b}$, but I don't know (a) if this is helpful and (b) how to prove it.

Can someone clarify what exactly the object is, and point me towards the next step?

Answer

The condition $f(x)\geq 0$ seems to kill all non-trivial possibilities: since $f(0)=0$ we let $y=-x:$

$$-f^2(2x)=4f(x)f(-x)$$

However $f(x)\geq 0$, so $f(x)=0$. Are you absolutely sure of the $\mathbb{R}\to [0,\infty)$ bit?

calculus - Computing Integral of $frac{sin^n x}{x^n}$

How do you compute $$\int_0^{\infty}\frac{\sin^n x}{x^n}dx$$ for every $n$? Thank you.

For $n=1$ it is widely known and for $n=2$ you might use Plancherel's formula. But I don't know how to do it for $n\geq3.$

number theory - Is there a polynomial $p(x)$ with integer coefficients such that $p(2013)=1789$ and $p(1515)=1830$?

Problem:
Is there a polynomial $p(x)$ with integer coefficients such that
$p(2013)=1789$ and $p(1515)=1830$?

My attempt:

After ruling out polynomials of degree 1, 2 and 3, and with further inspection, it appeared to me that such a polynomial doesn't exist.

Is my below proof accurate?

---

Suppose that $p$ exists, and let

$q(x)=p(x)-1789$ and $s(x)=p(x)-1830$

then, $q(2013)=0$ and $s(1515)=0$, so clearly,

$q(x)=(x-2013)f(x)$ and $s(x)=(x-1515)g(x)$,

for some polynomials $f$ and $g$ with integer coefficients.

Let $a$, $c$ and $d$ be the constant terms of $p$, $g$ and $f$, respectively, and observe that the constant terms of $s$ and $q$ are

$-1515c=a-1830 \ $ and $-2013d=a-1789$, $ \ $ respectively. $ \ \ \ \ \ \
(*)$

Thus,

$a \equiv 1830 \equiv 315 \pmod{1515}$ and $a \equiv 1789 \pmod{2013}$.

But this system of congruence doesn't have a simultaneous solution (since $ \gcd(1515, 2013)\not\mid 1789-315$).

Hence, there's no integer value of $a$ that satisfies $(*)$, which is a contradiction.
Therefore, $p$ doesn't exist.

---

If the above is correct, is there perhaps a more direct way of proving this?

Answer

$p(2013)-p(1515)$ is divisible by $2013-1515=498,$ but $1789-1830=-41$ is not.

It follows from the following reasoning.

Let $p(x)=a_0x^n+a_1x^{n-1}+...+a_n,$ where $a_i\in\mathbb Z$.

Thus, $$p(m)-p(k)=a_0(m^n-k^n)+a_1(m^{n-1}-k^{n-1})+...+a_{n-1}(m-k)=$$
$$=(m-k)(a_0(m^{n-1}+m^{n-2}k+...+k^{n-1})+a_1(m^{n-2}+...+k^{n-2})+...+a_{n-1}).$$

abstract algebra - Representing Elementary Functions in a CAS

I've looked through several books about computer algebra. They are surprisingly scarce about how to actually represent elementary functions.

Basically, as far as I understood elementary functions are roughly

$$\textbf{Quot}\left(\mathbb K[x, \exp x, \exp x^2 \log x, \ldots] \right)$$

that is rational functions over field $\mathbb K$, with variables (or kernels) $x$, $\exp x$, $\exp x^2$, $\log x$ and so on. Other function can be added.

However it doesn't seem possible to have a finite set of kernels to represent what is meant by elementary functions. For example it should contain all kernels of the form $\exp x^n$ or $\exp \exp \ldots \exp x$. And no way you can just enumerate an infinite set within a CAS.

Apparently the algebraic treatment of elementary functions lacks the notion of composition of functions.

How is composition introduced?

What is the algebraic treatment of elementary functions that can be fed to a computer?

Answer

I've resolved the issue and my concerns in the FriCAS mailing list. I just thought one cannot define two types that would refer to each other, but I was wrong.

integration - A closed-form expression for $int_0^infty frac{ln (1+x^alpha) ln (1+x^{-beta})}{x} , mathrm{d} x$

I have been trying to evaluate the following family of integrals:

$$ f:(0,\infty)^2 \rightarrow \mathbb{R} \, , \, f(\alpha,\beta) = \int \limits_0^\infty \frac{\ln (1+x^\alpha) \ln (1+x^{-\beta})}{x} \, \mathrm{d} x \, . $$

The changes of variables $\frac{1}{x} \rightarrow x$, $x^\alpha \rightarrow x$ and $x^\beta \rightarrow x$ yield the symmetry properties
$$ \tag{1}
f(\alpha,\beta) = f(\beta,\alpha) = \frac{1}{\alpha} f\left(1,\frac{\beta}{\alpha}\right) = \frac{1}{\alpha} f\left(\frac{\beta}{\alpha},1\right) = \frac{1}{\beta} f\left(\frac{\alpha}{\beta},1\right) = \frac{1}{\beta} f\left(1,\frac{\alpha}{\beta}\right) $$

for $\alpha,\beta > 0$ .

Using this result one readily computes $f(1,1) = 2 \zeta (3)$ . Then $(1)$ implies that
$$ f(\alpha,\alpha) = \frac{2}{\alpha} \zeta (3) $$
holds for $\alpha > 0$ . Every other case can be reduced to finding $f(1,\gamma)$ for $\gamma > 1$ using $(1)$.

An approach based on xpaul's answer to this question employs Tonelli's theorem to write
$$ \tag{2}
f(1, \gamma) = \int \limits_0^\infty \int \limits_0^1 \int \limits_0^1 \frac{\mathrm{d}u \, \mathrm{d}v \, \mathrm{d}x}{(1+ux)(v+x^\gamma)} = \int \limits_0^1 \int \limits_0^1 \int \limits_0^\infty \frac{\mathrm{d}x \, \mathrm{d}u \, \mathrm{d}v}{(1+ux)(v+x^\gamma)} \, .$$
The special case $f(1,2) = \pi \mathrm{C} - \frac{3}{8} \zeta (3)$ is then derived via partial fraction decomposition ($\mathrm{C}$ is Catalan's constant). This technique should work at least for $\gamma \in \mathbb{N}$ (it also provides an alternative way to find $f(1,1)$), but I would imagine that the calculations become increasingly complicated for larger $\gamma$ .

Mathematica manages to evaluate $f(1,\gamma)$ in terms of $\mathrm{C}$, $\zeta(3)$ and an acceptably nice finite sum of values of the trigamma function $\psi_1$ for some small, rational values of $\gamma > 1$ (before resorting to expressions involving the Meijer G-function for larger arguments). This gives me some hope for a general formula, though I have not yet been able to recognise a pattern.

Therefore my question is:

How can we compute $f(1,\gamma)$ for general (or at least integer/rational) values of $\gamma > 1$ ?

Update 1:

Symbolic and numerical evaluations with Mathematica strongly suggest that
$$ f(1, n) = \frac{1}{n (2 \pi)^{n-1}} \mathrm{G}_{n+3, n+3}^{n+3,n+1} \left(\begin{matrix} 0, 0, \frac{1}{n}, \dots, \frac{n-1}{n}, 1 , 1 \\ 0,0,0,0,\frac{1}{n}, \dots, \frac{n-1}{n} \end{matrix} \middle| \, 1 \right) $$
holds for $n \in \mathbb{N}$ . These values of the Meijer G-function admit an evaluation in terms of $\zeta(3)$ and $\psi_1 \left(\frac{1}{n}\right), \dots, \psi_1 \left(\frac{n-1}{n}\right) $ at least for small (but likely all) $n \in \mathbb{N}$ .

Interesting side note: The limit
$$ \lim_{\gamma \rightarrow \infty} f(1,\gamma+1) - f(1,\gamma) = \frac{3}{4} \zeta(3) $$
follows from the definition.

Update 2:

Assume that $m, n \in \mathbb{N} $ are relatively prime (i.e. $\gcd(m,n) = 1$). Then the expression for $f(m,n)$ given in Sangchul Lee's answer can be reduced to
\begin{align}
f(m,n) &= \frac{2}{m^2 n^2} \operatorname{Li}_3 ((-1)^{m+n}) \\
&\phantom{=} - \frac{\pi}{4 m^2 n} \sum \limits_{j=1}^{m-1} (-1)^j \csc\left(j \frac{n}{m} \pi \right) \left[\psi_1 \left(\frac{j}{2m}\right) + (-1)^{m+n} \psi_1 \left(\frac{m + j}{2m}\right) \right] \\
&\phantom{=} - \frac{\pi}{4 n^2 m} \sum \limits_{k=1}^{n-1} (-1)^k \csc\left(k \frac{m}{n} \pi \right) \left[\psi_1 \left(\frac{k}{2n}\right) + (-1)^{n+m} \psi_1 \left(\frac{n + k}{2n}\right) \right] \\
&\equiv F(m,n) \, .
\end{align}
Further simplifications depend on the parity of $m$ and $n$.

This result can be used to obtain a solution for arbitrary rational arguments: For $\frac{n_1}{d_1} , \frac{n_2}{d_2} \in \mathbb{Q}^+$ equation $(1)$ yields
\begin{align}
f\left(\frac{n_1}{d_1},\frac{n_2}{d_2}\right) &= \frac{d_1}{n_1} f \left(1,\frac{n_2 d_1}{n_1 d_2}\right) = \frac{d_1}{n_1} f \left(1,\frac{n_2 d_1 / \gcd(n_1 d_2,n_2 d_1)}{n_1 d_2 / \gcd(n_1 d_2,n_2 d_1)}\right) \\
&= \frac{d_1 d_2}{\gcd(n_1 d_2,n_2 d_1)} f\left(\frac{n_1 d_2}{\gcd(n_1 d_2,n_2 d_1)},\frac{n_2 d_1}{\gcd(n_1 d_2,n_2 d_1)}\right) \\
&= \frac{d_1 d_2}{\gcd(n_1 d_2,n_2 d_1)} F\left(\frac{n_1 d_2}{\gcd(n_1 d_2,n_2 d_1)},\frac{n_2 d_1}{\gcd(n_1 d_2,n_2 d_1)}\right) \, .
\end{align}

Therefore I consider the problem solved in the case of rational arguments. Irrational arguments can be approximated by fractions, but if anyone can come up with a general solution: you are most welcome to share it. ;)

Answer

Only a comment. We have

$$ \int_{0}^{\infty} \frac{\log(1+\alpha x)\log(1+\beta/x)}{x} \, dx = 2\operatorname{Li}_3(\alpha\beta) - \operatorname{Li}_2(\alpha\beta)\log(\alpha\beta) $$

which is valid initially for $\alpha, \beta > 0$ and extends to a larger domain by the principle of analytic continuation. Then for integers $m, n \geq 1$ we obtain

\begin{align*}
f(m, n)
&=\int_{0}^{\infty} \frac{\log(1+x^m)\log(1+x^{-n})}{x}\,dx \\
&\hspace{6em} = \sum_{j=0}^{m-1}\sum_{k=0}^{n-1} \left[ 2\operatorname{Li}_3\left(e^{i(\alpha_j+\beta_k)}\right) - i(\alpha_j+\beta_k)\operatorname{Li}_2\left(e^{i(\alpha_j+\beta_k)}\right) \right],
\end{align*}

where $\alpha_j = \frac{2j-m+1}{n}\pi$ and $\beta_k = \frac{2k-n+1}{n}\pi$. (Although we cannot always split complex logarithms, this happens to work in the above situation.) By the multiplication formula, this simplifies to

\begin{align*}
f(m, n)
&= \frac{2\gcd(m,n)^3}{m^2n^2}\operatorname{Li}_3\left((-1)^{(m+n)/\gcd(m,n)}\right) \\
&\hspace{2em} - \frac{i}{n} \sum_{j=0}^{m-1} \alpha_j \operatorname{Li}_2\left((-1)^{n-1}e^{in\alpha_j}\right) \\
&\hspace{2em} - \frac{i}{m} \sum_{k=0}^{n-1} \beta_k \operatorname{Li}_2\left((-1)^{m-1}e^{im\beta_k}\right).
\end{align*}

Here, $\gcd(m,n)$ is the greatest common divisor of $m$ and $n$.

---

The following code tests the above formula.