Wikipedia:Reference desk/Mathematics

Welcome to the mathematics section
of the Wikipedia reference desk.

skip to bottom

Select a section:

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

Want a faster answer?

Main page: Help searching Wikipedia

   

How can I get my question answered?

• Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
• Post your question to only one section, providing a short header that gives the topic of your question.
• Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
• Don't post personal contact information – it will be removed. Any answers will be provided here.
• Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
• Note:
  • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
  • We don't answer requests for opinions, predictions or debate.
  • We don't do your homework for you, though we'll help you past the stuck point.
  • We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

Ready? Ask a new question!

How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

• The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.

See also:

• Teahouse
• Help desk
• Village pump
• Help manual

July 2

Array of random values

Given a 2-dimensional array of random values (think of a noisy image) how do you construct an autocorrelation filter that will converge on a given point in the array starting anywhere in the array (or almost anywhere) Philvoids (talk) 15:41, 2 July 2024 (UTC)

Does this answer your question?

1. Compute the two-dimensional discrete Fourier transform of the image (for which you can use the two-dimensional version of the fast Fourier transform algorithm).
2. Filter out the high spatial frequencies.
3. Compute the inverse transform.

 --Lambiam 17:54, 2 July 2024 (UTC)

A numerical test
The following discussion has been closed. Please do not modify it.
Below is an 8x8 array of numbers. Start from any one of 64 locations ranging from (x0,y0) = (0,0) bottom left to (7,7) top right. Can you show a formula whose input (x0,y0) always yields as output (X,Y) = (3,3) ? Y ^ | | 7 247 51 132 34 223 6 121 243 6 81 196 176 224 77 159 211 171 5 119 245 56 244 141 247 33 115 4 254 49 175 170 95 19 208 108 3 118 204 145 117 25 242 162 229 2 35 200 250 115 45 62 229 135 1 212 219 232 186 196 59 68 74 0 192 207 14 129 102 13 28 65 0 1 2 3 4 5 6 7 -->X

Philvoids (talk) 09:08, 3 July 2024 (UTC)

I have a hard time understanding the question. What does it mean for a formula (or an algorithm) to "start from a location"? The constant function $(x_{0},y_{0})\mapsto (3,3)$ trivially meets the requirement, but this cannot be what you are looking for. If the output should be the same, regardless of $(x_{0},y_{0}),$ why is this location supplied as input? I assume that the matrix of values is also part of the input. What is it about these values that makes $(3,3)$ the desired output?  --Lambiam 12:03, 3 July 2024 (UTC)

I have a hard time understanding it as well. I don't know what an "autocorrelation filter" is either, but maybe that's just me. I know what autocorrelation is, and I know what a filter is, but the two words together don't seem to have any special meaning and a Google search wasn't very enlightening. A filter would, according to my understanding of the meaning in this context, produce an array from a another array. The generic application of a filter would produce a sequence from another sequence. For example a noise filter would take, for example, an audio file, and remove the noise producing another file with just the speech or music or whatever. You can use the same idea with two dimensional arrays to clean up images, or three dimensional arrays to clean up video. (This is basically what Lambiam's original answer would do.) Such arrays are typically highly autocorrolated and the outputs of a noise filter would be more so, but I don't see how that translates to "autocorrelation filter". In any case, the question seems to want not an array as output, but a location within the array. In general you have to be more specific about what the function is supposed to do, not just give an example. If I ask for a function with f(2)=4, it could be f(x)=x² or x+2 or just 4; there's not enough information in the question to get a meaningful answer. --RDBury (talk) 16:06, 3 July 2024 (UTC)

"Given a 2-dimensional array" - it could be any array and in the test example I give an 8x8 array of integers. That is a given data.(It could be a different array, maybe larger.) "Start anywhere in the array" - there are 64 locations in the example array and you can start at (0,0) or (0,1) or (0,2) or...all the way up to (7,7). Whatever formula or procedure or algorithm you provide MUST ALWAYS yield as output the arbitrary (means I chose it) location x=3, y=3 i.e. (3,3) that happens to hold the value 117 in the example. I don't know whether you can manage it, and you may have difficulty with the corner or edge locations. But if you can't solve the question, maybe you can reword it for everyone better than I have managed. Philvoids (talk) 20:27, 3 July 2024 (UTC)

Define function $f:\mathbb {Z} ^{2}\to \mathbb {Z} ^{2}$ by

$f(i,j)=(3,3).$

If that does not solve your problem, can you explain how this falls short?  --Lambiam 21:26, 3 July 2024 (UTC)

@Lambiam Your first response described how you would use an FFT and its inverse to remove high frequency "noise" from the array data. Your latest response abandons the reader to define a map conversion. Philvoids (talk) 14:55, 4 July 2024 (UTC)

I do not understand what problem you are trying to solve. Given how you restated it, my latest response should – using my best effort in interpreting the restatement – be a solution (in fact, the only solution). Since I also understand that it can't be this simple, your pointing out in some detail in which respects it does not satisfy the requirements for being a solution might, perhaps, help me get some grip on what problem you are trying to solve. At the moment, I am totally clueless.  --Lambiam 17:31, 4 July 2024 (UTC)

I do not understand these problem statements either. Is the intended output an input? If it's not an input then how is an independent oracle going about computing the output? Otherwise, "f(x,y) times zero plus i" and "f(x,y) minus f(x,y) plus j" are just a few of many arithmetic formula that take the values at any f(x,y) as inputs and are negated, and thus always return indexes i and j as input for some value at f(i,j). Modocc (talk) 21:02, 4 July 2024 (UTC)

Perhaps it would help to give some context to the problem instead of trying to state it in the abstract. What does the array represent? What does a position on the array represent? If we had the real world situation you're trying to deal with then maybe the problem you're trying to solve would be self-evident. --RDBury (talk) 21:32, 4 July 2024 (UTC)

The context for my question is my interest in efficient software to perform Image stitching, Document mosaicing or extraction of unlimited large-area maps from multiple map patches screen dumped from sites such as Google Maps. In each case we begin with a pair of images (which are 2D arrays of pixel values) that are known to overlap partly, but the exact offset between them has to be found before we can join them seamlessly. Stitching map patches together seems relatively easy because with correct offset there will be 100% correlation between the images in their overlap area; this is an autocorrelation because the pixels come from one master map. Consider my 8x8 array example as part of a map overlap area; we make a rough guess of the x-y offset of the overlapping map. Allow that the guess is likely inaccurate, which becomes apparent if we look for the pixel value at position (x,y)=(3,3) on the second map, and are disapointed to find it is not 117. We know all the array values and its size suggests there is one correct offset and 63 wrong offsets.

Pseudocode for a clumsy stitching
The following discussion has been closed. Please do not modify it.
define maparray(8,8) x=0 y=0 v=maparray(0,0) while v != maparray(3,3) {x++ if x==8 then x=0, y++ if y==8 then print "No match found." v=maparray(x,y) } print "Update offset by x:",-x," y:",-y Deficiencies of this code are - Up to 63 comparisons can be be needed before the correct offset is found - Noise causing false positive(s) or failure is not considered in my question but it arises when stitching photographs. The clumsy routine lacks noise tolerance because a 1 or 2 unit deviation at (3,3) disables the search, or causes a false positive at (3,2), (0,3), (0,5) or (7,5). That is regarding the array byte values that could represent 256 grey levels; I think that the error probabilities in hardware are independent of bit weightings and I find that there are 13 locations whose values have 2 or less [[Hamming distance]] from the value in (3,3) that was used for searching.

Ideas for an improved algorithm

- A larger array may be needed for a larger overlap area

- Sequential search costs time and computation effort but is only necessary where there is no gradient to follow towards the correct offset.

- False positives that arise from noise when searching for one pixel value may be reduced by searching for blocks of pixel values, such as the combination of (3,3), (4,3), (3,4) and (4,4). Philvoids (talk) 20:05, 5 July 2024 (UTC)

The commonly used methods for photo stitching and for document mosaicing involve feature detection, which can be seen as a (possible very rudimentary) way of interpreting the images. You appear to be seeking an approach that is, so to speak, interpretation-free.

In your pseudocode there is only one map, but a stitching algorithm needs two maps as input. Very abstractly, the general problem involves

• a set of domains,
• a group of transformations on domains, and
• a codomain.

A "map" is then a function from a domain to a codomain.

Moreover, there is

• a goodness of fit measure that expresses the similarity between two maps.

Given a map $m:D\to C$ and a domain transformation $\tau ,$ we can define

$\tau [\![m]\!]=m\circ \tau .$

The problem is now, given two maps $m_{1}$ and $m_{2},$ to determine a transformation $\tau$ that maximizes the goodness of fit between $m_{1}$ and $\tau [\![m_{2}]\!].$ Ideally, the latter is the same as the goodness of fit between $\tau ^{{-}1}[\![m_{!}]\!]$ and $m_{2},$ so that the problem is symmetric.

In your case the domains are rectangular subsets of $\mathbb {Z} ^{2}$ and the codomain is the set of integers or real numbers, but it could also be the set of values of some colour model. The domain transformations are translations of the elements of a domain. The measure for goodness of fit could be the correlation (not "autocorrelation") between $m_{1}$ and $\tau [\![m_{2}]\!].$ restricted to the intersection of their domains. Depending on the application, other measures may give better results.

I am not aware of efficient algorithms for your version of the general problem, but here is an approach that I expect to work well for certain types of images – but not so well on some other types.

The basic idea is to find the best shift for scaled-down versions of the images. The scaled-back-up shift should be close to the optimal one; simple hill climbing should quickly lead to an optimum. This can be applied recursively, but scaling down too much may turn the images into featureless blurs for which the goodness of fit is a meaningless measure.  --Lambiam 13:49, 6 July 2024 (UTC)

The only thing I'd add is that it seems to me that creating such an algorithm from scratch is reinventing the wheel. Hugin is open source, stable (or so they claim), and available for download. I can understand wanting to "roll your own" if you really want to understand the algorithms, but there is a lot of specialized knowledge involved and you should at least have a general idea what actually goes into the programs. There is more than you might think, such as adjusting for differences in lighting and perspective. "I hear, I forget. I see, I remember. I do, I understand," as the proverb goes, But we can't always the spare the man-years needed to skip the "I hear" and "I see" stages. --RDBury (talk) 03:02, 7 July 2024 (UTC)

July 7

Using sagemath or an other language, how to exactly find out what the order of the base point of an elliptic curve in Edwards Form is ?

This kind of code will do it for the usual Weirestrass form :

a = 1
b = 3141592653589793238462643383279502884197169399375105820974944592307816406665
p = 2^251 + 17*2^192 +1

E = EllipticCurve(GF(p), [0,0,0,a,b])
print(E)
print(E.abelian_group())

card = E.cardinality()
print("cardinality =",card)
factor(card)

G = E(874739451078007766457464989774322083649278607533249481151382481072868806602,152666792071518830868575557812948353041420400780739481342941381225525861407)
print("Generator order q=", G.order())

But how to do it for a curve in the twisted Edwards form ? Because I suppose converting the curve and the point to the Weirestrass form would change the resulting order being computed right ? 2A01:E0A:401:A7C0:DD6F:EA1B:CCA4:2633 (talk) 21:12, 7 July 2024 (UTC)

I'm not an expert, but I'd think that the group is isomorphic to the Weierstrass group by which it is induced.  --Lambiam 11:07, 8 July 2024 (UTC)

July 8

If 0 and 1 are counted as perfect powers, can every sufficiently large number be written as the sum of 3 perfect powers?

If 0 and 1 are counted as perfect powers, can every sufficiently large number be written as the sum of 3 perfect powers? 1.165.223.46 (talk) 12:09, 8 July 2024 (UTC)

Are you including perfect powers of negative numbers?

example: the first problematic number is 7, which cannot be made from 3 powers of positive numbers, but using negative numbers, 7 = 2^3 + (-1)^3 + 0^3. Dhrm77 (talk) 14:40, 8 July 2024 (UTC)

Every sufficiently large number, of course I know that 7 and 15 cannot be written as such. 220.132.216.52 (talk) 17:09, 8 July 2024 (UTC)

[edited: This comment addresses a different problem]: A necessary condition for an integer $n$ to equal such a sum a sum of three cubes is that $n$ does not equal 4 or 5 modulo 9, because the cubes modulo 9 are 0, 1, and −1, and no three of these numbers can sum to 4 or 5 modulo 9. For the remaining set of integers it is an open problem; see Sums of three cubes.  --Lambiam 16:10, 8 July 2024 (UTC)

No, I only consider nonnegative numbers. 220.132.216.52 (talk) 17:08, 8 July 2024 (UTC)

It would seem that no one knows, see OEIS:A113505. GalacticShoe (talk) 17:32, 8 July 2024 (UTC)

I'm confused. 32 is congruent to 5 mod 9, but it's the sum of 1 perfect power. All numbers not congruent to 7 mod 8 are a sum of three squares so you only have to consider 7, 15, 23, 31, ... The OEIS entry does not cite a source, other than just letting the program run to 10⁸ (which seems feasible). But in general if OEIS doesn't know then it's probably unknown. --RDBury (talk) 01:28, 9 July 2024 (UTC)

There's also the slightly-more restrictive OEIS:A135393 that doesn't use 0 or 1 as perfect powers, and even then the list seems to probably be finite. This makes me wonder what would happen if you removed the nonnegativity constraint from the base of the power. Certainly many terms would disappear (like $335=3^{5}+10^{2}+(-2)^{3}$), and it seems likely that every number not congruent to $4$ or $5\!\!\!{\pmod {9}}$ would be erased as per the sums of three cubes, but the remaining terms might be interesting. GalacticShoe (talk) 04:26, 9 July 2024 (UTC)

335 is in fact 7^3 + (-2)^3 2402:7500:943:2AC:F4A8:5238:E22:338A (talk) 06:31, 9 July 2024 (UTC)

Yes, but I wanted to give an example without using -1, 0, or 1. Although there are easy examples like $167=13^{2}+(-1)^{3}+(-1)^{3}$, I'd like to know if there are more without using the more trivial perfect powers. GalacticShoe (talk) 07:38, 9 July 2024 (UTC)

Are there infinitely many positive integers that are not the sum of two perfect powers? (If 0 and 1 are counted as perfect powers) 2402:7500:943:2AC:F4A8:5238:E22:338A (talk) 06:31, 9 July 2024 (UTC)

The number of perfect powers up to $N$ is (if I'm not mistaken) asymptotically equal to ${\sqrt {N}}.$ Then there are $\Omega (N^{\frac {3}{2}})$ triples of perfect powers whose sum is at most $N.$ Thus, unless there is some number-theoretic conspiracy that makes many triple sums unexpectedly often have the same value, one expects, by a naive counting argument, saturation: not only can eventually all numbers be expected to be the sum of three perfect powers, but to be so in many ways.  --Lambiam 12:03, 9 July 2024 (UTC)

For N congruent to 7 mod 8 you need at least one odd power. So I think the number of triples you can use for these N is more like $\Omega (N^{\frac {4}{3}})$. The exponent is still greater than 1 though. The asymptotic density of numbers which are the sum of three squares is 7/8 and for two squares it's 0. In these cases your tuple counting argument would estimate densities of $\Omega (N^{\frac {3}{2}})$ and $\Omega (N)$ respectively, but there are indeed "number-theoretic conspiracies" in both cases. --RDBury (talk) 03:56, 10 July 2024 (UTC)

This additional question is “are there infinitely many positive integers that are not the sum of two perfect powers?” 49.217.131.145 (talk) 12:42, 10 July 2024 (UTC)

I think Lambiam's tuple counting argument with a tweak or two settles this. If N is congruent to 3 mod for then there must be an odd power. The number of perfect powers less than N is asymptotically ${\sqrt {N}}$ and the number of of odd powers is asymptotically ${\sqrt[{3}]{N}}.$ The number of combinations is then $\Omega (N^{\frac {5}{6}})$ which is asymptotically less than N/4. I didn't see an OEIS entry for this, but that may be because I was trying to work out the first few terms in my head. Sequence A075434 comes close, but they're not counting 0 as a perfect power so it includes 4, 27, ... . --RDBury (talk) 17:26, 10 July 2024 (UTC)