# Reduce over integers - why does MMA not give ~impossible?

I know that Reduce is not Solve but from e.g. 212880 I also see that integer solutions may be found by it. However, I am clearly confused about what I should expect from it and why.

Consider this system of equations

$$2^x = 3 k + 1 \land 2^{x-1} = 3 m + 1$$

By inspection there are no solutions. If we put the question to MMA (11.0.1) like this

Block[{x, k, m}, Reduce[2^x == 3 k + 1 && 2^(x - 1) == 3 m + 1, {x, k, m}, Integers]]


We obtain (via TeXForm)

$$(k|m|x)\in \mathbb{Z}\land k=\frac{2^x}{3}-\frac{1}{3}\land m=\frac{2^{x-1}}{3}-\frac{1}{3}$$

Q1 Why does MMA not realise that the forms of $$k, m$$ are incompatible?

Q2 Why does MMA state "$$(k|m|x)\in Integers$$" as Alternatives? The reduction is specified over the integers so they must all be integers simultaneously. Specifically, why is it not expressed as an And of each $$\in$$ Integers?

Q3 Summary: is it basically just saying that there is no reduction of the equations?

NB if I reduce over {x, k}, or {x, m} MMA returns False, which I might interpret as there being no solution, but why should I pick these variable pairs? Note that Reduce over {k, m} does not return False

UPDATE Summary of new & selected points from various responses.

From the documentation, the first line of Details and Options, says that the result of Reduce" always describes exactly the same mathematical set as expr.", and a further example further down confirms that False means there is no solution.

Ordering of variables is important: Reduce[..., {k, m, x}] = False i.e. it does give "~impossible".

Reduce might, like FindInstance be unable to provide an answer, but unlike the latter may not know that it can't and may not say so to the user.

From the documentation, $$Element[x1|x2|...,dom]$$ asserts that all the $$x_i$$ are elements of dom. (The justification for using this form to express is still wanting)

Note that $$2^x$$ is not integral for integer $$x<0$$

• Q2: This is well documented. You can read it as follows: Whichever of the 3 alternatives (variables) you take, it is an integer. Oct 21, 2022 at 17:43
• Comment about Q1: FindInstance[2^x==3 k+1&&2^(x-1)==3 m+1,{x,k,m},Integers] returns no solution and says "The methods available to FindInstance are insufficient to find the requested instances or prove they do not exist." V12.3. Another example with similar behavior is FindInstance[{2^a==2*b+1,b>0},{a,b},Integers]. Oct 21, 2022 at 17:46
• @user293787 Did you perhaps mean the info on Alternatives? (I checked it previously.) It functions as an "or" like construct, and, working inclusively includes all. The question is I suppose a language design question. Why not list the elements joined by And? Is there something that Alternatives enables that the And construction wouldn't? Oct 21, 2022 at 20:59
• No, I meant the info in the documentation on Element, see the 3rd syntax there. It says "Element[x1|x2|...,dom] asserts that all the xi are elements of dom". Oct 22, 2022 at 1:25
• Not sure, but Reduce[2^x == 3 k + 1 && 2^(x - 1) == 3 m + 1, {k, m, x}, Integers] works. Polynomial equations -- not ones with "transcendental" terms, or at least not with exponential terms -- are the principal domain of Reduce. Possibly Reduce does not analyze exponential terms unless "asked." The order of the variables matters in Reduce: The later variables are solved in terms of the earlier ones. You need x not to be first in the list. Oct 22, 2022 at 2:04

Reduce[2^x == 3 k + 1 && 2^(x - 1) == 3 m + 1, {x}, Integers]


False

If we using {x,k,m} as variable, MMA will try to give all the expression of all the variable {x,k,m},it maybe exceed the ability of MMA. If we only set {x}, MMA will refer {k,m} as parametric variables, this make it focus the relation between {x} and {k,m},that is we need to help MMA in this cases.

This can be done with Mathematica in such a way.

NMinimize[{(2^x - 3 k - 1)^2 + (2^(x - 1) - 3 m - 1)^2,
x \[Element] Integers && m \[Element] Integers &&  k \[Element] Integers}, {x, m, k}]


{0.25, {x -> 0, m -> 0, k -> 0}}

The above result implies there is no solution of the system under consideration over the integers.

Addition. I think the result of (y=2^x)

FunctionConvexity[(y - 3 k - 1)^2 + (y/2 - 3 m - 1)^2, {y, k, m}]


1

guarantees the found minimum over the integers is global.

NMinimize[{(y - 3 k - 1)^2 + (y/2 - 3 m - 1)^2, {y, k, m} \[Element]  Integers}, {y, k, m}]


{0.25,{y->1,k->0,m->0}}

implies {0.25, {x -> 0, m -> 0, k -> 0}} is the global minimum of (2^x - 3 k - 1)^2 + (2^(x - 1) - 3 m - 1)^2 over the integers since the global minimum of the convex function over the superset $$\mathbb Z^3$$ equals the minimum over the set $$\{2^x|x\in \mathbb Z\}\times\mathbb Z^2$$. Hope I am clear.

Addition 3. As @user293787 pointed out, $$2^x$$ is not an integer if $$x$$ is a negative integer. For this case

NMinimize[{(y - 3 k - 1)^2 + (y/2 - 3 m - 1)^2, {k, m} \[Element]
Integers && y > 0 && y <= 1}, {y, k, m}]


{0.25, {y -> 1., k -> 0, m -> 0}}

completes the job.

• But... NMinimize[{(x^3+y^3-z^3)^2,Element[x|y|z,PositiveIntegers]},{x,y,z}] returns {1.,{x->1,y->1,z->1}}. Do you consider that a proof of the $n=3$ case of a famous theorem? The documentation says: "If f and cons are linear or convex, the result given by NMinimize will be the global minimum, over both real and integer values; otherwise, the result may sometimes only be a local minimum. " Oct 21, 2022 at 18:14
• @user293787: Thank you for your valuable comment. At least, the command FunctionConvexity[(2^x - 3 k - 1)^2 + (2^(x - 1) - 3 m - 1)^2, {k, m}, Assumptions -> x \[Element] Reals] results in 1. Oct 21, 2022 at 18:27
• Just to clarify, the question is fundamentally about how Reduce works; the non-existence of a solution can be established by various means. This minimisation trick is new to me - duly noted! Oct 21, 2022 at 21:07
• One more thing: $2^x$ is not an integer if $x$ is a negative integer. Oct 22, 2022 at 1:36
• Not buying this convexity argument. With a slight change: In:= FunctionConvexity[(2^x - 3 k - 2)^2 + (2^(x - 1) - 3 m - 1)^2, {k, m}, Assumptions -> x \[Element] Reals] Out= 1 In:= NMinimize[{(2^x - 3 k - 2)^2 + (2^(x - 1) - 3 m - 1)^2, x >= 1, k >= 0, m >= 0, {x, k, m} \[Element] Integers}, {x, k, m}] Out= {0., {x -> 1, k -> 0, m -> 0}} But notice the solution is not unique. In:= (2^x - 3 k - 2)^2 + (2^(x - 1) - 3 m - 1)^2 /. {x -> 3, m -> 1, k -> 2} Out= 0 Oct 22, 2022 at 17:26