Proof of proveit.physics.quantum.QPE._modabs_in_full_domain_simp theorem

import proveit
theory = proveit.Theory() # the theorem's theory
from proveit import l, x, N, defaults
from proveit.numbers import (
        zero, one, two, Div, greater_eq, Less, Mult, Neg, subtract)
from proveit.numbers.modular import mod_abs_x_reduce_to_abs_x
from proveit.physics.quantum.QPE import (
        _t_in_natural_pos, _two_pow_t, _two_pow__t_minus_one,
        _two_pow_t_is_nat_pos)

%proving _modabs_in_full_domain_simp

With these allowed/disallowed theorem/theory presumptions (e.g., to avoid circular dependencies), we begin our proof of
_modabs_in_full_domain_simp:
(see dependencies)

defaults.assumptions = _modabs_in_full_domain_simp.all_conditions()

defaults.assumptions:

# for convenience
l_membership = _modabs_in_full_domain_simp.condition

l_membership:

We plan to instantiate the following mod_abs_x_reduce_to_abs_x theorem with $x: \ell$ and $N = 2^t$, the challenging piece of which is to establish that $|\ell|\le\frac{2^t}{2}=2^{t-1}$:

mod_abs_x_reduce_to_abs_x

 ⊢  

Establish an upper bound on $|\ell|$, and along the way establish some properties of the $\ell$ bounds $2^{t-1}$ and $-2^{t-1}+1$ so their absolute values will eventually be (automatically) simplified and so we can also evaluate a Max() on the values.

from proveit.numbers.absolute_value import weak_upper_bound_asym_interval
weak_upper_bound_asym_interval

 ⊢  

temp_bound_01 = _two_pow__t_minus_one.deduce_bound(_t_in_natural_pos.derive_element_lower_bound())

temp_bound_01:  ⊢  

From temp_bound_01, we can also automatically derive $-2^{t-1}\ge -1$ and $-2^{t-1}+1\ge 0$ as needed (through canonical forms).

# temp_bound_02 = temp_bound_01.left_mult_both_sides(Neg(one))

# temp_bound_03 = temp_bound_02.right_add_both_sides(one)

# Want to explicitly establish this, so the eventual Max() evaluation
# will go through in the instantiation of abs_l_max_bound further below
Less(subtract(temp_bound_01.lhs, one), temp_bound_01.lhs).prove()

 ⊢  

Since we know $-2^{t-1}+1 \le 0$ and $0 < 2^{t-1}-1 < 2^{t-1}$, when we instantiate the weak_upper_bound_asym_interval theorem, the absolute values are simplified, and since we have pre-established the relative size of $2^{t-1}-1$ and $2^{t-1}$, the Max() operation can be simplified:

from proveit import a, b, c
_a_sub, _b_sub, _c_sub = (
    l,
    l_membership.domain.lower_bound,
    l_membership.domain.upper_bound)
abs_l_max_bound = weak_upper_bound_asym_interval.instantiate(
    {a: _a_sub, b: _b_sub, c: _c_sub})

abs_l_max_bound:  ⊢  

Now we're ready to instantiate the mod_abs_x_reduce_to_abs_x theorem

# here we set auto_simplify=False, else we simply obtain the unhelpful |ell|=|ell|
mod_abs_x_reduce_to_abs_x.instantiate({x: l, N: _two_pow_t}, auto_simplify=False)

 ⊢  

_modabs_in_full_domain_simp may now be readily provable (assuming required theorems are usable).  Simply execute "%qed".

%qed

proveit.physics.quantum.QPE._modabs_in_full_domain_simp has been proven.

	step type	requirements	statement
0	generalization	1	⊢
1	instantiation	2, 12, 3, 4	⊢
	: , :
2	conjecture		⊢
	proveit.numbers.modular.mod_abs_x_reduce_to_abs_x
3	instantiation	208, 5, 6	⊢
	: , : , :
4	instantiation	7, 8, 9	⊢
	: , : , :
5	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.rational_pos_within_real_pos
6	instantiation	208, 10, 168	⊢
	: , : , :
7	theorem		⊢
	proveit.logic.equality.sub_right_side_into
8	instantiation	11, 12, 13, 86, 14, 15*	⊢
	: , : , :
9	instantiation	131, 121, 16, 17	⊢
	: , : , : , :
10	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.nat_pos_within_rational_pos
11	conjecture		⊢
	proveit.numbers.absolute_value.weak_upper_bound_asym_interval
12	instantiation	208, 197, 18	⊢
	: , : , :
13	instantiation	208, 197, 19	⊢
	: , : , :
14	instantiation	20, 21, 22	⊢
	: , :
15	instantiation	115, 23, 24	⊢
	: , : , :
16	instantiation	146, 25	⊢
	: , : , :
17	instantiation	144, 26	⊢
	: , :
18	instantiation	208, 204, 27	⊢
	: , : , :
19	instantiation	208, 204, 51	⊢
	: , : , :
20	theorem		⊢
	proveit.logic.booleans.conjunction.and_if_both
21	instantiation	28, 51, 111, 39	⊢
	: , : , :
22	instantiation	29, 51, 111, 39	⊢
	: , : , :
23	instantiation	70, 210, 30, 31, 32, 33	⊢
	: , : , : , :
24	instantiation	115, 34, 35	⊢
	: , : , :
25	instantiation	146, 167	⊢
	: , : , :
26	instantiation	36, 138, 179, 166, 37*	⊢
	: , :
27	instantiation	208, 38, 39	⊢
	: , : , :
28	conjecture		⊢
	proveit.numbers.number_sets.integers.interval_lower_bound
29	conjecture		⊢
	proveit.numbers.number_sets.integers.interval_upper_bound
30	instantiation	135	⊢
	: , :
31	instantiation	135	⊢
	: , :
32	instantiation	40, 41, 42*	⊢
	:
33	instantiation	43, 44	⊢
	:
34	instantiation	45, 94, 86	⊢
	: , :
35	instantiation	46, 86, 94, 47*	⊢
	: , :
36	conjecture		⊢
	proveit.numbers.division.div_as_mult
37	instantiation	115, 48, 49	⊢
	: , : , :
38	instantiation	50, 51, 111	⊢
	: , :
39	assumption		⊢
40	conjecture		⊢
	proveit.numbers.absolute_value.abs_neg_elim
41	instantiation	52, 76, 176, 86, 53, 54*, 55*	⊢
	: , : , :
42	instantiation	56, 64, 164, 57*	⊢
	: , :
43	conjecture		⊢
	proveit.numbers.absolute_value.abs_non_neg_elim
44	instantiation	90, 58	⊢
	: , :
45	conjecture		⊢
	proveit.numbers.ordering.max_bin_args_commute
46	axiom		⊢
	proveit.numbers.ordering.max_def_bin
47	instantiation	115, 59, 60	⊢
	: , : , :
48	instantiation	146, 61	⊢
	: , : , :
49	instantiation	62, 138, 63	⊢
	: , :
50	conjecture		⊢
	proveit.numbers.number_sets.integers.int_interval_within_int
51	instantiation	152, 88, 196	⊢
	: , :
52	conjecture		⊢
	proveit.numbers.addition.weak_bound_via_left_term_bound
53	instantiation	171, 118	⊢
	:
54	instantiation	157, 164, 64	⊢
	: , :
55	instantiation	115, 65, 66	⊢
	: , : , :
56	conjecture		⊢
	proveit.numbers.negation.distribute_neg_through_binary_sum
57	instantiation	67, 68	⊢
	:
58	instantiation	69, 118	⊢
	:
59	instantiation	70, 210, 71, 72, 73, 74	⊢
	: , : , : , :
60	instantiation	75, 123, 203, 125	⊢
	: , : , : , : , :
61	instantiation	161, 162, 207, 167*	⊢
	: , :
62	conjecture		⊢
	proveit.numbers.multiplication.commutation
63	instantiation	148, 164, 179, 166	⊢
	: , :
64	instantiation	208, 188, 76	⊢
	: , : , :
65	instantiation	115, 77, 78	⊢
	: , : , :
66	instantiation	79, 127, 104	⊢
	: , :
67	conjecture		⊢
	proveit.numbers.negation.double_negation
68	instantiation	208, 188, 86	⊢
	: , : , :
69	conjecture		⊢
	proveit.numbers.number_sets.natural_numbers.natural_pos_is_pos
70	axiom		⊢
	proveit.core_expr_types.operations.operands_substitution
71	instantiation	135	⊢
	: , :
72	instantiation	135	⊢
	: , :
73	instantiation	80, 87	⊢
	: , :
74	instantiation	81, 82	⊢
	: , :
75	axiom		⊢
	proveit.core_expr_types.conditionals.true_case_reduction
76	instantiation	208, 197, 83	⊢
	: , : , :
77	instantiation	146, 121	⊢
	: , : , :
78	instantiation	146, 84	⊢
	: , : , :
79	conjecture		⊢
	proveit.numbers.addition.subtraction.add_cancel_basic
80	conjecture		⊢
	proveit.core_expr_types.conditionals.satisfied_condition_reduction
81	conjecture		⊢
	proveit.core_expr_types.conditionals.dissatisfied_condition_reduction
82	instantiation	85, 94, 86, 87	⊢
	: , :
83	instantiation	208, 204, 88	⊢
	: , : , :
84	instantiation	146, 121	⊢
	: , : , :
85	conjecture		⊢
	proveit.numbers.ordering.not_less_from_less_eq
86	instantiation	208, 197, 89	⊢
	: , : , :
87	instantiation	90, 91	⊢
	: , :
88	instantiation	92, 111	⊢
	:
89	instantiation	208, 204, 111	⊢
	: , : , :
90	conjecture		⊢
	proveit.numbers.ordering.relax_less
91	instantiation	93, 94, 95, 176, 96, 97*, 98*	⊢
	: , : , :
92	conjecture		⊢
	proveit.numbers.negation.int_closure
93	conjecture		⊢
	proveit.numbers.addition.strong_bound_via_left_term_bound
94	instantiation	208, 197, 99	⊢
	: , : , :
95	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.zero_is_real
96	conjecture		⊢
	proveit.numbers.numerals.decimals.less_0_1
97	instantiation	131, 100, 101, 102	⊢
	: , : , : , :
98	instantiation	131, 103, 104, 105	⊢
	: , : , : , :
99	instantiation	208, 204, 106	⊢
	: , : , :
100	instantiation	115, 107, 108	⊢
	: , : , :
101	instantiation	139	⊢
	:
102	instantiation	144, 114	⊢
	: , :
103	instantiation	115, 109, 110	⊢
	: , : , :
104	instantiation	139	⊢
	:
105	instantiation	144, 121	⊢
	: , :
106	instantiation	152, 111, 154	⊢
	: , :
107	instantiation	146, 114	⊢
	: , : , :
108	instantiation	115, 112, 113	⊢
	: , : , :
109	instantiation	146, 114	⊢
	: , : , :
110	instantiation	115, 116, 117	⊢
	: , : , :
111	instantiation	208, 169, 118	⊢
	: , : , :
112	instantiation	122, 203, 210, 123, 124, 125, 119, 127, 159	⊢
	: , : , : , : , : , :
113	instantiation	120, 123, 210, 125, 124, 127, 159	⊢
	: , : , : , :
114	instantiation	146, 121	⊢
	: , : , :
115	axiom		⊢
	proveit.logic.equality.equals_transitivity
116	instantiation	122, 203, 210, 123, 124, 125, 164, 127, 159	⊢
	: , : , : , : , : , :
117	instantiation	126, 164, 127, 128	⊢
	: , : , :
118	instantiation	129, 210, 130	⊢
	: , :
119	conjecture		⊢
	proveit.numbers.number_sets.complex_numbers.zero_is_complex
120	conjecture		⊢
	proveit.numbers.addition.elim_zero_any
121	instantiation	131, 132, 133, 134	⊢
	: , : , : , :
122	conjecture		⊢
	proveit.numbers.addition.disassociation
123	axiom		⊢
	proveit.numbers.number_sets.natural_numbers.zero_in_nats
124	instantiation	135	⊢
	: , :
125	conjecture		⊢
	proveit.core_expr_types.tuples.tuple_len_0_typical_eq
126	conjecture		⊢
	proveit.numbers.addition.subtraction.add_cancel_triple_13
127	instantiation	136, 137, 138	⊢
	: , :
128	instantiation	139	⊢
	:
129	conjecture		⊢
	proveit.numbers.exponentiation.exp_natpos_closure
130	instantiation	140, 141, 142	⊢
	:
131	conjecture		⊢
	proveit.logic.equality.four_chain_transitivity
132	instantiation	146, 143	⊢
	: , : , :
133	instantiation	144, 145	⊢
	: , :
134	instantiation	146, 147	⊢
	: , : , :
135	conjecture		⊢
	proveit.numbers.numerals.decimals.tuple_len_2_typical_eq
136	conjecture		⊢
	proveit.numbers.multiplication.mult_complex_closure_bin
137	instantiation	148, 164, 149, 150	⊢
	: , :
138	instantiation	208, 188, 151	⊢
	: , : , :
139	axiom		⊢
	proveit.logic.equality.equals_reflexivity
140	conjecture		⊢
	proveit.numbers.number_sets.integers.nonneg_int_is_natural
141	instantiation	152, 153, 154	⊢
	: , :
142	instantiation	155, 156	⊢
	: , :
143	instantiation	157, 158, 159	⊢
	: , :
144	theorem		⊢
	proveit.logic.equality.equals_reversal
145	instantiation	160, 179, 173, 172, 166	⊢
	: , : , :
146	axiom		⊢
	proveit.logic.equality.substitution
147	instantiation	161, 162, 207	⊢
	: , :
148	conjecture		⊢
	proveit.numbers.division.div_complex_closure
149	instantiation	163, 179, 164	⊢
	: , :
150	instantiation	165, 166, 167	⊢
	: , : , :
151	instantiation	180, 181, 168	⊢
	: , : , :
152	conjecture		⊢
	proveit.numbers.addition.add_int_closure_bin
153	instantiation	208, 169, 182	⊢
	: , : , :
154	instantiation	208, 170, 200	⊢
	: , : , :
155	conjecture		⊢
	proveit.numbers.addition.subtraction.nonneg_difference
156	instantiation	171, 182	⊢
	:
157	conjecture		⊢
	proveit.numbers.addition.commutation
158	instantiation	208, 188, 172	⊢
	: , : , :
159	instantiation	208, 188, 173	⊢
	: , : , :
160	conjecture		⊢
	proveit.numbers.exponentiation.product_of_real_powers
161	conjecture		⊢
	proveit.numbers.exponentiation.neg_power_as_div
162	instantiation	208, 174, 175	⊢
	: , : , :
163	conjecture		⊢
	proveit.numbers.exponentiation.exp_complex_closure
164	instantiation	208, 188, 176	⊢
	: , : , :
165	theorem		⊢
	proveit.logic.equality.sub_left_side_into
166	instantiation	177, 202	⊢
	:
167	instantiation	178, 179	⊢
	:
168	conjecture		⊢
	proveit.physics.quantum.QPE._two_pow_t_is_nat_pos
169	conjecture		⊢
	proveit.numbers.number_sets.integers.nat_pos_within_int
170	conjecture		⊢
	proveit.numbers.number_sets.integers.neg_int_within_int
171	conjecture		⊢
	proveit.numbers.number_sets.natural_numbers.natural_pos_lower_bound
172	instantiation	180, 181, 182	⊢
	: , : , :
173	instantiation	208, 183, 184	⊢
	: , : , :
174	conjecture		⊢
	proveit.numbers.number_sets.complex_numbers.real_nonzero_within_complex_nonzero
175	instantiation	208, 185, 186	⊢
	: , : , :
176	instantiation	208, 197, 187	⊢
	: , : , :
177	conjecture		⊢
	proveit.numbers.number_sets.natural_numbers.nonzero_if_is_nat_pos
178	conjecture		⊢
	proveit.numbers.exponentiation.complex_x_to_first_power_is_x
179	instantiation	208, 188, 189	⊢
	: , : , :
180	theorem		⊢
	proveit.logic.sets.inclusion.unfold_subset_eq
181	instantiation	190, 191	⊢
	: , :
182	axiom		⊢
	proveit.physics.quantum.QPE._t_in_natural_pos
183	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.real_neg_within_real
184	instantiation	208, 192, 193	⊢
	: , : , :
185	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.rational_nonzero_within_real_nonzero
186	instantiation	208, 194, 195	⊢
	: , : , :
187	instantiation	208, 204, 196	⊢
	: , : , :
188	conjecture		⊢
	proveit.numbers.number_sets.complex_numbers.real_within_complex
189	instantiation	208, 197, 198	⊢
	: , : , :
190	theorem		⊢
	proveit.logic.sets.inclusion.relax_proper_subset
191	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.nat_pos_within_real
192	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.rational_neg_within_real_neg
193	instantiation	208, 199, 200	⊢
	: , : , :
194	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.nonzero_int_within_rational_nonzero
195	instantiation	208, 201, 202	⊢
	: , : , :
196	instantiation	208, 209, 203	⊢
	: , : , :
197	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.rational_within_real
198	instantiation	208, 204, 205	⊢
	: , : , :
199	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.neg_int_within_rational_neg
200	instantiation	206, 207	⊢
	:
201	conjecture		⊢
	proveit.numbers.number_sets.integers.nat_pos_within_nonzero_int
202	conjecture		⊢
	proveit.numbers.numerals.decimals.posnat2
203	theorem		⊢
	proveit.numbers.numerals.decimals.nat1
204	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.int_within_rational
205	instantiation	208, 209, 210	⊢
	: , : , :
206	conjecture		⊢
	proveit.numbers.negation.int_neg_closure
207	conjecture		⊢
	proveit.numbers.numerals.decimals.posnat1
208	theorem		⊢
	proveit.logic.sets.inclusion.superset_membership_from_proper_subset
209	conjecture		⊢
	proveit.numbers.number_sets.integers.nat_within_int
210	conjecture		⊢
	proveit.numbers.numerals.decimals.nat2
*equality replacement requirements