Complexity is compatible with chaotic state

[spencerthayer]

The paper Chaos and complexity by design by Daniel A. Roberts and Beni Yoshida refutes your “findings” by demonstrating how seemingly designed phenomena are compatible with chaotic systems.

We study the relationship between quantum chaos and pseudorandomness by developing probes of unitary design. A natural probe of randomness is the “frame potential,” which is minimized by unitary k-designs and measures the 2-norm dis- tance between the Haar random unitary ensemble and another ensemble. A natural probe of quantum chaos is out-of-time-order (OTO) four-point correlation functions. We show that the norm squared of a generalization of out-of-time-order 2k-point correlators is proportional to the kth frame potential, providing a quantitative con- nection between chaos and pseudorandomness. Additionally, we prove that these 2k-point correlators for Pauli operators completely determine the k-fold channel of an ensemble of unitary operators. Finally, we use a counting argument to obtain a lower bound on the quantum circuit complexity in terms of the frame potential. This provides a direct link between chaos, complexity, and randomness.

[avaneev]

What do you mean by "seemingly designed phenomena are compatible"? The abstract refers to concepts I've never studied. I suggest you to check yourself or point authors to the program code, and decide whether or not a linear system can produce chaos or randomness at all. Probably, you are trying to compare apples to oranges here. The culprit is comparative complexities of a "chaos" system and prvhash1.

[avaneev]

Also I'm assuming you've meant "intelligent impulses" by a "finding" since you didn't specify which part of prvhash you are debating.

[avaneev]

I'll point to this article: https://en.wikipedia.org/wiki/Chaos_theory From "Minimum complexity of a chaotic system": Finite-dimensional linear systems are never chaotic.

[avaneev]

I'll add that prvhash1 features a "hash" ring-buffer in feedback mode. In DSP engineering field this concept is known as "feedback delay line", and it is considered a linear operator, an LTI system.

[dfischer]

I'll add that prvhash1 features a "hash" ring-buffer in feedback mode. In DSP engineering field this concept is known as "feedback delay line", and it is considered a linear operator, an LTI system.

https://codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game-of-life/142675#142675

related?

[etheory]

I'll add that prvhash1 features a "hash" ring-buffer in feedback mode. In DSP engineering field this concept is known as "feedback delay line", and it is considered a linear operator, an LTI system.

The TR-909 uses exactly the same method for it's white noise generator, and it is chaotic. So I'm not sure why you are so confused here. It uses a 1 bit binary multi-stage ring-buffer. It's easily seen in the schematic. This design is incredibly well used and documented for chaotic systems. It's not new or novel in any way whatsoever. Also, a ring-buffer is not an LTI system of it employs feedback (as your hash does), so your entire thesis is not really correct. If you put any input into a ring-buffer with feedback, it recirculates forever, hence a new input at a different time will not produce the same output. Hence, not LTI. Also a linear system does not imply LTI, so I think you are mixing up terms here.

[avaneev]

If you put any input into a ring-buffer with feedback, it recirculates forever, hence a new input at a different time will not produce the same output. Hence, not LTI. Also a linear system does not imply LTI, so I think you are mixing up terms here.

Well, you are obviously not into DSP terms. A simple 1st order IIR filter also "recirculates" its output, but it's a linear time-invariant system as well. It's linear in mathematical terms; how it visibly behaves is out of the question. The difference between 1st order IIR filter and feedback delay line is in the mathematical order.

[avaneev]

The TR-909 uses exactly the same method for it's white noise generator, and it is chaotic.

On this, I'll note that my point is that prvhash-1 output can be far from being visibly chaotic, and the results are presented. You are missing something from the description. No reason to compare prvhash-1 to something "chaotic" when it's obviously non-chaotic.

[etheory]

If you put any input into a ring-buffer with feedback, it recirculates forever, hence a new input at a different time will not produce the same output. Hence, not LTI. Also a linear system does not imply LTI, so I think you are mixing up terms here.

Well, you are obviously not into DSP terms. A simple 1st order IIR filter also "recirculates" its output, but it's a linear time-invariant system as well. It's linear in mathematical terms; how it visibly behaves is out of the question. The difference between 1st order IIR filter and feedback delay line is in the mathematical order.

It is linear if the feedback coefficients are less than unity, due to the fact this ensures the system is stable, and decays over time. This further ensures that the time shift invariance of the system is preserved. Your system does not have this property, so it's not LTI, because your ring-buffer feedback coefficients are unity, hence the system is chaotic.

[avaneev]

It is linear if the feedback coefficients are less than unity, due to the fact this ensures the system is stable, and decays over time. This further ensures that the time shift invariance of the system is preserved. Your system does not have this property, so it's not LTI, because your ring-buffer feedback coefficients are unity, hence the system is chaotic.

I think you are making things up. LTI is about transfer function, shift invariance, and causality. Coefficients are out of the question.

[etheory]

It is linear if the feedback coefficients are less than unity, due to the fact this ensures the system is stable, and decays over time. This further ensures that the time shift invariance of the system is preserved. Your system does not have this property, so it's not LTI, because your ring-buffer feedback coefficients are unity, hence the system is chaotic.

I think you are making things up. LTI is about transfer function, shift invariance, and causality. Coefficients are out of the question.

You need to read more then. A linear system where any coefficient is greater or equal to unity and there is feedback will not have shift invariance. This is quite obvious.

[avaneev]

I'll give you an example of sinewave oscillator, also presented at the project page:

    const double tmp = svalue1;
    svalue1 = sincr * svalue1 - svalue2;
    svalue2 = tmp;

It has feedback coefficient of -1, and it is stable.

[etheory]

I'll give you an example of sinewave oscillator, also presented at the project page:

  const double tmp = svalue1;
  svalue1 = sincr * svalue1 - svalue2;
  svalue2 = tmp;

It has feedback coefficient of -1, and it is stable.

But it is not an LTI system. Which was my point. It does not have shift invariance.

[avaneev]

You need to read more then. A linear system where any coefficient is greater or equal to unity and there is feedback will not have shift invariance. This is quite obvious.

"read more", "quite obvious". These are non-substantiated responses. Shift invariance does not depend on the oscillatory length of the filter, as it mainly depends on the linearity of transformation.

[etheory]

"read more", "quite obvious". These are non-substantiated responses. Shift invariance does not depend on the oscillatory length of the filter, as it mainly depends on the linearity of transformation. Your sinewave example is NOT shift invariant, hence not LTI.

Read the definition here: https://en.wikipedia.org/wiki/Shift-invariant_system which clearly explains my point.

[avaneev]

Read the definition here: https://en.wikipedia.org/wiki/Shift-invariant_system which clearly explains my point.

Well, I know this definition, but it does not imply "coefficients dependence" or your opinion on how a function visually behaves.

[avaneev]

I'll add that I'm not an educator, and my explanations may have mistakes, but this is irrelevant. You are facing the reality of the results, while I have no scientific degrees to be any soft of authority to you, be my conclusions right or wrong. So far responses of mathematicians were seriously negative, which means at the moment you won't find authoritative support to my claims. Time will tell...

[avaneev]

I'll explain what LTI means in case of a feedback delay line. It means that at whatever position its read-write pointer is the moment the input signal arrives, it will produce the same output. Since delay lines have a linear transfer function (note that we are talking about S/Z domain linearity), they can be reversed or "deconvolved". The Seed and lcg variables can be perceived as 1-tap (1st order) delay lines. So, I think that for the claim prvhash-1 is non-linear to be valid, one has to prove prvhash-1 is irreversible, but I think one would have a hard time proving this.

[avaneev]

Of course, irreversibility is just a strong indicator of a non-linear function (some non-linear functions are reversible). However, as prvhash-1 is dealing with overflowing 1-bit additions, this may be close to irreversible saturation. On the other hand, addition in F_2 is assumed to be linear (why would not it be?). At the same time, in some practical situations, one may change non-linear logical operators to linear F_2 additions. Which in my opinion means that in F_2, the edge between linearity and non-linearity is smeared. Unfortunately, that complicates understanding even further. But I stand by my opinion that prvhash-1 is linear in F_2 until someone shows it is irreversible.

[avaneev]

I'll give you an example of sinewave oscillator, also presented at the project page: But it is not an LTI system. Which was my point. It does not have shift invariance.

Sorry, but you are just completely wrong here. In canonical Direct Form I, it can be written as:

    y[n] = 1*x[n] - sincr*y[n-1] - y[n-2]

To function as an oscillator from its initial zero-state, it has to be fed with a single unit impulse, with all other x[n] being zero. You may input a unit impulse at any moment, which means it is an LTI system. Subsequent unit impulses (if any) will increase or decrease oscillation's amplitude.

[avaneev]

@etheory I've studied the TR-909 noise generator reference, and it's not the same thing. LFSR is closer to usual and well-known multi-bit PRNGs. https://electricdruid.net/practical-lfsr-random-number-generators/