# Product Configuration in Answer Set Programming

Seemran Mishra
University of Potsdam  Germany

###### Abstract

Abstract. This is a preliminary work on configuration knowledge representation
which serves as a foundation for building interactive configuration systems in
Answer Set Programming (ASP). The major concepts of the product configuration
problem are identified and discussed with a bike configuration example. A fact
format is developed for expressing product knowledge that is domain-specific
and can be mapped from other systems. Finally, a domain-independent ASP
encoding is provided that represents the concepts in the configuration
problem.

##  1 Introduction

Product configuration is one of the most successful commercial applications of
artificial intelligence techniques [20] [4]. It has been used from telephone
switching systems [23], to smart home configurations [5], in cement
manufacturing plants [19], and the automotive industry [24]. Being highly
dynamic, this field evolved from mass production to mass customisation [25],
as the customer needs became more individualistic. The recent trend is
interactive configuration [2], where the user is involved in every step of the
configuration process.

ASP [10] is a declarative modeling approach used for product configuration. In
fact, product configuration was one of the first practical applications of ASP
[21]. Since then, there have been many works that use ASP to represent product
configuration [9] [18] [5]. But most of them are either domain-specific or
tackle a subset of the configuration problem. Others express product knowledge
in form of ASP rules. This requires domain-experts to be proficient in ASP,
which is not always the case.

This work serves as a foundation for interactive configuration systems in ASP.
The motivation here is the identification of the major concepts related to
product configuration and the corresponding representation in ASP. The
development of a domain-independent configuration knowledge representation is
another motivation. This can be achieved by a clear separation between product
knowledge and configuration knowledge. The advantage here is that the
configuration knowledge can be reused for any product to be configured and
ensures better system maintenance. Stress is given for representing product
knowledge as facts, to facilitate seamless mapping from other systems. This
enables domain-experts to provide product knowledge without being experts in
ASP [26].

This paper is organized as follows: In Section 2, a background on product
configuration is given. The configuration problem is described in Section 3
using bike configuration as an example. An ASP-based representation of the
configuration problem and the corresponding solution is given in Section 4.
Finally, the future work is expressed in Section 5.

##  2 Background

One of the earliest applications of product configuration was R1/XCON, built
on a rule-based representation language, where the solving knowledge was
intertwined with domain-specific configuration knowledge [15]. The trend
quickly evolved to model-based knowledge representation where there is a clear
separation of problem solving knowledge from domain-specific configuration
knowledge. As the industry shifted from mass production to mass customisation,
another boundary between domain-specific configuration knowledge and user
requirements was drawn [17].

To create a general understanding of configuration, [22] introduced concepts
like component types, properties and constraints like partof that are
discussed in detail in the Section 3. Also, the configuration is classified to
connection-based, structure-based, resource-based, and function-based
approaches. Most concepts used in this work is adapted from [22] and [12].

Representation and modeling of configuration knowledge have been split into
three categories, namely constraint-based, graphical and logic-based knowledge
representation [12]. Constraint programming has been one of the major used
techniques for product configuration. Starting with static constraint
satisfaction where all the variables had to be assigned values, the switch was
done to dynamic constraint satisfaction [16], where the configuration
variables can be activated and deactivated during the search process. Owing to
the lack of support for component-oriented modelling in the previous
techniques, generative constraint satisfaction (GCSP) [23] emerged. GCSP was
designed for product configuration and has widespread uses in the industry.

The main graphic-based representation systems used for constraint satisfaction
are feature models and UML component diagrams [14], [6]. These systems improve
the accessibility of configuration knowledge to domain experts who are not
acquainted with modeling, since these systems are more understandable and
maintainable. Predicate, as well as description logic, have been used for
representing configuration problems, along with a mapping from UML diagrams
[6].

ASP has been used widely in product configuration [21] [24]. Linux Package
Configuration in [9] is another interesting application of ASP. An ASP
representation of a configuration problem in the context of feature models is
given in [18]. Mapping of object-oriented concepts to ASP directed at product
configuration in UML was shown in [3]. In [5], an introductory example of
representing smart home configurations in ASP is provided.

##  3 Product Configuration Problem

In this section, some of the major concepts used in product configuration are
described in the context of bike configuration. The building blocks of a
configuration problem are components. The components in the bike configuration
problem consist of a bike, a frame, two wheels namely the front wheel and the
rear wheel, a stand, and a basket as shown in Figure 1. The domain of each
component in the configuration problem is a set of component type, shortened
to type. Examples of types include w1, w2, and w3 which are in the domain of
both the front wheel and the rear wheel.

A component is characterized by a set of properties. The types also have
properties, whose values are predefined. For example, the material of frame
type f1 is aluminum. The domain of component properties apart from type is
given by the predefined property values of the corresponding types of
components. As an example in the bike configuration example, the material of
the frame can be either carbon fiber or aluminum. To make the representation
more uniform, type is considered as a property of the component.

A configuration problem can be defined as a set of components with properties,
a set of domains for each component property, and a set of constraints listed
below:

  * •

Property Assignment: These constraints deal with the assignment of values to
component properties from their respective domains.

    * –

A1: Every component present in the configuration solution must be assigned a
type.

    * –

A2: A component property can only have one value.

    * –

A3: The values assigned to a component property must exactly correspond to the
predefined property values of the type it is assigned.

    * –

A4: All mandatory properties of a component should be assigned values if the
component is in a configuration solution.

  * •

Partonomy: The structure of a product can be represented as a partonomy where
a whole component may have optional and mandatory parts. For example, a bike
is a whole component while a frame is a mandatory part and a basket is an
optional part of the bike.

    * –

P1: If a part component is present in an assignment, the whole component must
be also in the configuration.

    * –

P2: If a component is present in an assignment, all the mandatory part
components have to be in the assignment.

  * •

Requirements: These constraints specify that including certain components
(with property values) forces other components (with property values) to be
present in the configuration.

    * –

R1: A component requires another component to be part of the solution.

    * –

R2: To satisfy the configuration, a component requires another component with
a specific property value to be assigned to the configuration (or vice versa).

    * –

R3: To satisfy the configuration, a component with a certain property value
requires another component with a specific property value to be assigned to
the configuration.

  * •

Incompatibility: These constraints specify that certain combinations of
components (with property values) are not allowed in the configuration
solution.

    * –

I1: Incompatible components cannot be together in a configured solution.

    * –

I2: A component can be incompatible with a certain presence value of another
component. In this case, if the former component is present in the solution,
then the later component can’t have the respective property value.

    * –

I3: The property value of a component can be incompatible with the property
value of another component. In this case, only one of the components and their
property value can be part of the solution or both have to be excluded.

  * •

User Requirements: The users can specify their requirements in terms of
components or specific values of component properties.

    * –

U1: Every component that the user requests, must be part of the configuration.

    * –

U2: A user can require a component with a specific property value. In this
case, the specified component with the respective property value must be
present in the solution.

    * –

U3: Every component that the user requests not to be present, must not be part
of the configuration.

    * –

U4: A user can require that a component with a specific property value is not
in the configuration. In this case, the specified component may be absent or
may be present with another value for the respective property in the solution.

A configuration solution is an assignment of values to component properties in
the configuration problem from their domains such that the constraints are
satisfied.

Listing 1: Bike configuration problem instance as facts

⬇

1domain(bike,type,city_bike). domain(bike,type,mountain_bike).

2domain(rear_wheel,type,w1).domain(rear_wheel,type,w2).

3domain(rear_wheel,type,w3).domain(front_wheel,type,w3).

4domain(front_wheel,type,w1).domain(front_wheel,type,w2).

5domain(frame,type,f1).domain(frame,type,f2). domain(frame,type,f3).

6domain(stand,type,s1). domain(basket,type,b1).

7

8property_val(f1,material,aluminium).property_val(f1,basket_support,true).

9property_val(f2,material,carbon_fiber).property_val(f2,basket_support,false).

10property_val(f3,basket_support,true).property_val(w1,material,aluminium).

11property_val(w1,size,28).property_val(w2,size,26).property_val(w3,size,28).

12property_val(w2,material,aluminium).property_val(w3,material,carbon_fiber).

13

14mandatory_property(frame,material).

15

16partof(bike,frame,mandatory).partof(bike,front_wheel,mandatory).

17partof(bike,rear_wheel,mandatory).partof(bike,basket,optional).

18partof(bike,stand,optional).

19

20incompatible_com_pv(basket,(bike,type,mountain_bike)).

21incompatible_pv_pv((front_wheel,size,26),(rear_wheel,size,28)).

22incompatible_pv_pv((front_wheel,size,28),(rear_wheel,size,26)).

23

24require_com_com(basket,stand).

25require_com_pv(basket,(frame,basket_support,true)).

26require_pv_pv((frame,material,aluminium),(front_wheel,material,aluminium)).

27

28user_com(req,bike).user_com(req,basket).user_com_pv(req,(front_wheel,size,26)).

##  4 Representing Configuration in ASP

###  4.1 Fact Format

Listing 1 shows an instance of the bike configuration problem shown in Figure
1. The predicate domain(C,P,V) expresses that some value V can be assigned to
an property P of a component C. Initially, domains of the type property of all
components are provided in Lines 1-6. The predicate property_val(T,P,V) shown
in Line 8-12 denotes that V is the predefined value of the property P of type
T. This predicate is also used to generate the domains of component properties
apart from type during preprocessing.

The predicate mandatory_property(C, P) in Line 14 is used to express the
mandatory property constraint A4, where P is a mandatory property of a
component C. During the preprocessing section of the encoding, the property
type is made a mandatory property for all components. Partonomy of the bike is
listed in Lines 16-18, where the predicate partof(C1,C2,V) expresses that a
component C2 is a mandatory or optional part of the component C1 depending on
the respective value of V. The first fact of Line 16 expresses that the frame
is a mandatory part of the bike while the fact Line 18 expresses that basket
is an optional part of the bike.

Product specific incompatibility relations I1-I3 are represented in fact
format in Line 20-22. The predicate incompatible_com_pv(C1,(C2,P2,V2)),
denotes an incompatibility relation I2 between a component C1) and a component
property value C2,P2,V2. For example, the fact in Line 20 expresses that a
mountain bike can’t have a basket. Incompatibility I3 between component
attribute values (C1,P1,V1) and (C2,P2,V2) in form of predicate
incompatible_pv_pv((C1,P1,V1), (C2,P2,V2)) is shown in Line 21-22, which
specifies that the front wheel and rear wheel can’t be of different sizes. It
can be noted that incompatible_com_com(C1,C2) to express incompatibility
between component C1 and C2 is not given in this use case.

The requirements between bike components R1-R3 are given in Line 24-26. The
condition R1 where component C1 requires C2 is expressed by predicate
require_com_com(C1, C2). For example, the fact in Line 24 expresses that a
basket requires a stand. Similarly, require_com_pv(C1, (C2,P2,V2)) expresses
R2 where a component C1 requires another component C2 with property value
P2,V2. This example is shown in Line 25 expresses where a basket requires the
frame to support a basket. Requirement R3 of component attribute value
(C2,P2,V2) by (C1,P1,V1) is in form of predicate require_pv_pv((C1,P1,V1),
(C2,P2,V2)). For example, in Line 26, the front wheel has to be made up of
aluminum if the frame is. Additionally, there is a predicate of form
require_com_pv((C1,P1,V1), C2), where presence of the component C1 with
property value P1,V1 requires the component C2, which hasn’t been used here.

Finally in Line 28, the user requirements are listed. Here user_com(req, C)
means that user requires the component C. In the example, the user requires a
bike and a basket. Users can also specify if they want the property P of
component C to have a value V, in form of the predicate user_com(req,
(C,P,V)). For example, the user requires the size of the front wheel should be
26 is given in the last fact of Line 28. The above two predicates express U1
and U2 respectively. U3 and U4 can be expressed in a similar way by replacing
req to nreq as the first arguement.

Listing 2: Configuration Problem Encoding

⬇

1domain(C,P,V) :- domain(C,type,T), property_val(T,P,V).

2mandatory_property(C,type) :- domain(C,_,_).

3require_com_com(Part,Whole) :- partof(Whole,Part,_).

4require_com_com(Whole,Part) :- partof(Whole,Part,mandatory).

5

6{assign(C,P,V): domain(C,P,V)}.

7component(C) :- assign(C,P,V).

8

9:- assign(C,P,V1), assign(C,P,V2), V1 < V2.

10

11:- component(C), mandatory_property(C,P), not assign(C,P,_).

12

13:- assign(C,type,T), assign(C,P,V), P != type , not property_val(T,P,V).

14:- assign(C,type,T), property_val(T,P,V), not assign(C,P,V).

15

16:- require_com_com(C1,C2), component(C1), not component(C2).

17:- require_com_pv(C1,(C2,P,V)), component(C1), not assign(C2,P,V).

18:- require_pv_com((C1,P,V),C2), assign(C1,P,V), not component(C2).

19:- require_pv_pv((C1,P1,V1),(C2,P2,V2)), assign(C1,P1,V1), not
assign(C2,P2,V2).

20

21:- incompatible_com_com(C1,C2), component(C1), component(C2).

22:- incompatible_com_pv(C1,(C2,P,V)), component(C1), assign(C2,P,V).

23:- incompatible_pv_pv((C1,P1,V1),(C2,P2,V2)), assign(C1,P1,V1),
assign(C2,P2,V2).

24

25:- user_com(req,C), not component(C).

26:- user_com_pv(req,(C,P,V)), not assign(C,P,V).

27:- user_com(nreq,C), component(C).

28:- user_com_pv(nreq,(C,P,V)), assign(C,P,V).

Figure 1: Bike Configuration in UML

###  4.2 Encoding and Solution

The encoding in Listing 2 is domain-independent and is separated into three
parts: preprocessing in Lines 1-4, generation in Line 6-7, and testing in the
remaining part.

In Line 1, the domains of the component properties are generated from the
predefined property values of their types. Assignment of values property of
the components from their domain is given by Line 6, in form of a choice rule.
Also, to keep track of the components that are present in the configuration
solution, the predicate component(C) is used in Line 7, where C is the
component.

The constraint A4, that all mandatory properties should be assigned a value if
the component is present, is represented in Line 11. Along with this, the
constraint A1 is expressed using Line 2, where the type of a component is set
as a mandatory property.

Constraint A2 is represented in Line 9, meaning that a component property
cannot have more than one value. Line 13 and 14 depict rule A3. Line 13
expresses that a component cannot have property values that the assigned type
doesn’t have. In addition, Line 14 expresses that the component must have all
the pre-defined property values of its assigned type.

The partonomy constraints P1 and P2 are mapped into requirement constraint R1,
expressed in Line 3 and 4. Line 3 expresses that the part of a whole component
requires the whole component. In addition, whole components require all their
mandatory components to be present is enforced in Line 4. The component
requirements are defined in Line 16-19. Line 16 states that a component can
require another component (R1). Rule R2 is represented by Lines 17 and 18
where a component can require a certain property value from another component
and vice versa. The last requirement case, that a component with a specific
property value requires another component with a specific property value is
represented by Line 19 (rule R3).

The incompatibility constraints are enforced in Lines 21-23. Line 28
translates constraint I1, where a component is incompatible with another
component. I2 is represented by Line 30. The last case that a component with a
certain property value is incompatible with another component with a specific
property value is done in Line 32 (I3).

The user requirements are represented in Line 25-28. A user can require a
certain component (U1) or a component with a specific property value (U2).
This is represented in Line 25 and 26 respectively. On the contrary, the user
can also deny certain components or attribute values to be in the
configuration (U3, U4) which is represented in Line 27 and 28.

Each predicate in the solution assign(C,A,V) is intended to express that the
component C with attribute A and value V is present in the solution. Given the
facts in Listing 1 and encoding in Listing 2, the solution is represented in
Listing 3. Since the user needs a basket that is incompatible with the
mountain bike, the user is assigned a city bike. Due to requirements in Lines
24 and 25 in Listing 1, stand is added to the configuration, and f1 is
selected as the frame. The wheel w2 is used as front wheel because of user
requirement. Due to incompatibility expressed in Line 21 of Listing 1, w2 is
also used as the rear wheel.

Listing 3: Bike Configuration Solution

⬇

1assign(bike,type,city_bike). assign(rear_wheel,type,w2).

2assign(front_wheel,type,w2). assign(frame,type,f1).

3assign(stand,type,s1). assign(front_wheel,material,aluminium).

4assign(frame,basket_support,true). assign(basket,type,b1).

5assign(frame,material,aluminium). assign(front_wheel,size,26).

6assign(rear_wheel,size,26). assign(rear_wheel,material,aluminium)

##  5 Future Work

This is a preliminary work with the final objective of developing an
interactive product configuration system [2] [11]. Identification and encoding
of more concepts such as resource constraints, default values, user
preferences among others would be the next step. Mapping from commonly used
graphical and constraint based configuration representation methods to ASP
should also be done. Interactive configuration has many construction zones
[26], including product recommendation, configuration diagnosis [13] and
explanation. Further investigation of these techniques in the context of ASP
is another objective. Finally, a major step would be implementation of these
interactive techniques using clingo [8] along with its sophisticated Python
API that allows a fine-grained handling of the solving process.

## References

  * [1]
  * [2] A. Falkner, A. Haselböck, G. Krames, G. Schenner, H. Schreiner & R. Taupe (2020): _Solver Requirements for Interactive Configuration._ Journal of Universal Computer Science 26(3), pp. 343–373.
  * [3] A. Falkner, A. Ryabokon, G. Schenner & K. Shchekotykhin (2015): _OOASP: Connecting Object-Oriented and Logic Programming_.  In F. Calimeri, G. Ianni & M. Truszczyński, editors: Proceedings of the Thirteenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’15), Lecture Notes in Artificial Intelligence 9345, Springer-Verlag, pp. 332–345, 10.1007/978-3-319-23264-5_28.
  * [4] A. Falkner & H. Schreiner (2014): _SIEMENS: Configuration and Reconfiguration in Industry_.  In Felfernig et al. [7], chapter 16, pp. 199–210, 10.1016/b978-0-12-415817-7.00016-5.
  * [5] A. Felfernig, A. Falkner, M. Atas, S. Erdeniz, C. Uran & P. Azzoni (2017): _ASP-based Knowledge Representations for IoT Configuration Scenarios_.  In L. Zhang & A. Haag, editors: Proceedings of the Nineteenth International Configuration Workshop (CONF’17), pp. 62–67.
  * [6] A. Felfernig, G. Friedrich, D. Jannach, M. Stumptner & M. Zanker (2003): _Configuration knowledge representations for Semantic Web applications_.  Artificial Intelligence for Engineering Design, Analysis and Manufacturing 17(1), pp. 31–50, 10.1017/s0890060403171041.
  * [7] A. Felfernig, L. Hotz, C. Bagley & J. Tiihonen, editors (2014): _Knowledge-Based Configuration: From Research to Business Cases_.  Elsevier/Morgan Kaufmann, 10.1016/b978-0-12-415817-7.00029-3.
  * [8] M. Gebser, R. Kaminski, B. Kaufmann & T. Schaub (2014): _Clingo = ASP + Control: Preliminary Report_.  In M. Leuschel & T. Schrijvers, editors: Technical Communications of the Thirtieth International Conference on Logic Programming (ICLP’14), Theory and Practice of Logic Programming, Online Supplement 14(4-5).  Available at http://arxiv.org/abs/1405.3694v1.
  * [9] M. Gebser, R. Kaminski & T. Schaub (2011): _aspcud: A Linux Package Configuration Tool Based on Answer Set Programming_.  In C. Drescher, I. Lynce & R. Treinen, editors: Proceedings of the Second International Workshop on Logics for Component Configuration (LoCoCo’11), Electronic Proceedings in Theoretical Computer Science (EPTCS) 65, pp. 12–25, 10.4204/eptcs.65.2.
  * [10] M. Gelfond & V. Lifschitz (1988): _The Stable Model Semantics for Logic Programming_.  In R. Kowalski & K. Bowen, editors: Proceedings of the Fifth International Conference and Symposium of Logic Programming (ICLP’88), MIT Press, pp. 1070–1080, 10.1201/b10397-6.
  * [11] P. Hertum, I. Dasseville, G. Janssens & M. Denecker (2017): _The KB paradigm and its application to interactive configuration_.  Theory and Practice of Logic Programming 17(1), pp. 91–117, 10.1007/978-3-319-28228-2_2.
  * [12] L. Hotz, A. Felfernig, M. Stumptner, A. Ryabokon, C. Bagley & K. Wolter (2014): _Configuration Knowledge Representation and Reasoning_.  In Felfernig et al. [7], chapter 6, pp. 41–72, 10.1016/b978-0-12-415817-7.00006-2.
  * [13] U. Junker (2004): _QUICKXPLAIN: Preferred Explanations and Relaxations for Over-Constrained Problems_.  In D. McGuinness & G. Ferguson, editors: Proceedings of the Nineteenth National Conference on Artificial Intelligence (AAAI’04), AAAI Press, pp. 167–172.
  * [14] D. Mailharro (1998): _A classification and constraint-based framework for configuration_.  Artificial Intelligence for Engineering Design, Analysis and Manufacturing 12(4), pp. 383–397, 10.1017/s0890060498124101.
  * [15] J. McDermott (1982): _R1: A Rule-Based Configurer of Computer Systems_.  Artificial Intelligence 19(1), pp. 39–88, 10.1016/0004-3702(82)90021-2.
  * [16] S. Mittal & B. Falkenhainer (1990): _Dynamic Constraint Satisfaction Problems_.  In H. Shrobe, T. Dietterich & W. Swartout, editors: Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI’90), AAAI Press, pp. 25–32.
  * [17] S. Mittal & F. Frayman (1989): _Towards a Generic Model of Configuraton Tasks_.  In N. Sridharan, editor: Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (IJCAI’89), Morgan Kaufmann Publishers, pp. 1395–1401.
  * [18] V. Myllärniemi, J. Tiihonen, M. Raatikainen & A. Felfernig (2014): _Using Answer Set Programming for Feature Model Representation and Configuration_.  In A. Felfernig, C. Forza & A. Haag, editors: Proceedings of the Sixteenth International Configuration Workshop (CONF’14), CEUR Workshop Proceedings 1220, CEUR-WS.org, pp. 1–8.
  * [19] K. Orsvärn & H. Bennick (2014): _Tacton: Use of Tacton Configurator at FLSmidth_.  In Felfernig et al. [7], chapter 17, pp. 211–218, 10.1016/b978-0-12-415817-7.00017-7.
  * [20] T. Soininen & I. Niemelä (1999): _Developing a declarative rule language for applications in product configuration_.  In G. Gupta, editor: Proceedings of the First International Workshop on Practical Aspects of Declarative Languages (PADL’99), Lecture Notes in Computer Science 1551, Springer-Verlag, pp. 305–319, 10.1007/3-540-49201-1_21.
  * [21] T. Soininen, I. Niemelä, J. Tiihonen & R. Sulonen (2001): _Representing Configuration Knowledge With Weight Constraint Rules._ In A. Provetti & T. Son, editors: Proceedings of the AAAI Spring Symposium on Answer Set Programming (ASP’01), AAAI/MIT Press, pp. 195–201.
  * [22] T. Soininen, J. Tiihonen, T. Männistö & R. Sulonen (1998): _Towards a general ontology of configuration_.  Artificial Intelligence for Engineering Design, Analysis and Manufacturing 12(4), pp. 357–372, 10.1017/s0890060498124083.
  * [23] M. Stumptner, G. Friedrich & A. Haselböck (1998): _Generative constraint-based configuration of large technical systems_.  Artificial Intelligence for Engineering Design, Analysis and Manufacturing 12(4), pp. 307–320, 10.1017/s0890060498124046.
  * [24] J. Tiihonen, M. Heiskala, A. Anderson & T. Soininen (2013): _WeCoTin - A practical logic-based sales configurator_.  AI Communications 26(1), pp. 99–131, 10.3233/aic-2012-0547.
  * [25] J. Tiihonen, T. Soininen, I. Niemelä & R. Sulonen (2003): _A Practical Tool for Mass-Customising Configurable Products_.  In A. Folkeson, K. Gralen, M. Norell & U. Sellgren, editors: Proceedings of the Fourteenth International Conference on Engineering Design (ICED’03), Design Society (DS), pp. 1290–1299.
  * [26] L. Zhang (2014): _Product configuration: a review of the state-of-the art and future research_.  International Journal of Production Research 52(21), pp. 6381–6398, 10.1080/00207543.2014.942012.


# There are infinitely many (-1,1)-Carmichael numbers

QI-YANG ZHENG  Department of Mathematics, Sun Yat-sen University(Zhuhai
Campus), Zhuhai<EMAIL_ADDRESS>
###### Abstract.

We prove that there exist infinitely many $(-1,1)$–Carmichael numbers, that
is, squarefree, composite integers $n$ such that $p+1\,|\,n-1$ for each prime
$p$ dividing $n$.

##  1\. Introduction

The well-known Fermat’s Little Theorem states that if $p$ is a prime, $p$
divides $a^{p}-a$ for each integers $a$. Carmichael numbers are composite
numbers which have this property, i.e. a positive composite integer $n$ is a
Carmichael number if $n$ divides $a^{n}-a$ for each integers $a$. In 1899,
Korselt [4] give a criterion for Carmichael numbers: $n$ is a Carmichael
number if and only if $n$ is squareefree and $p-1\,|\,n-1$ for each prime $p$
dividing $n$.

Now we define a series of numbers satisfying some conditions analogous to
Korselt’s criterion.

######  Definition 1.1.

A positive squarefree composite number $n$ is an $(a,b)$-Carmichael numbers if
$n\neq b$ and $p-a\,|\,n-b$ for each prime $p$ dividing $n$.

The condition of squarefree eliminates some trivial cases. For example, cube
of prime numbers are $(-1,-1)$-Carmichael numbers, since
$p^{3}+1=(p+1)(p^{2}-p+1)$.

Under the definition, $(1,1)$-Carmichael numbers are the usual Carmichael
numbers; $(-1,-1)$-Carmichael numbers are known as Lucas-Carmichael numbers;
$(k,k)$-Carmichael numbers are known as $k$-Korselt numbers.

These numbers play an important role in various primality tests. Thus we are
interested in the properties of these numbers. Alford, Granville and Pomerance
[1] proved that there are infinitely many Carmichael numbers and stated that

One can modify our proof to show that for any fixed non-zero integer $a$,
there are infinitely many squarefree, composite integers $n$ such that $p-a$
divides $n-1$ for all primes $p$ dividing $n$.

In our notation it is equivalent to prove that there are infinitely many
$(a,1)$-Carmichael numbers with $a$ is non-zero. However, there are no any
result about infinitude of $(a,1)$-Carmichael numbers but $a=1$. In 2018,
Wright [8] proved that there are infinitely many $(-1,-1)$-Carmichael numbers,
or Lucas-Carmichael numbers.

In this paper, we prove that there are infinitely many $(-1,1)$-Carmichael
numbers, that is, squarefree, composite integers $n$ such that $p-a\,|\,n-1$
for each prime $p$ dividing $n$. The smallest one of $(-1,1)$-Carmichael
numbers is $385=5\times 7\times 11$. One can see more examples in OEIS/A225711
[7]. The method we used is a modification of [1].

######  Definition 1.2.

If $a$, $b$ are integers, we define $C(x;a,b)$ as the numbers of
$(a,b)$-Carmichael numbers not exceeding $x$.

We will use $C(x)$ in the place of $C(x;-1,1)$ in this paper for convenience.
In particular, we prove that $C(x)>x^{0.29}$ for all sufficiently large values
of $x$. We believe that there is some gap between $x^{0.29}$ and the true size
of $C(x)$, but it is enough to prove the infinitude of $(-1,1)$-Carmichael
numbers.

Let $\pi(x)$ be the numbers of primes $p\leq x$. For a fixed non-zero integer
$a$, let $\pi_{a}(x,y)$ be the number of primes $a<p\leq x$ for which $p-a$ is
free of prime factors exceeding $y$. From [3] we have

(1.1) $\pi_{a}(x,x^{1-E})\geq\gamma(E)\frac{x}{\log x}$

for any $x\geq x_{1}$ and all non-zero integer $a$;
$E\in(0,1-(2\sqrt{e})^{-1})$; $\gamma(E)$ is a constant depends on $E$;
$x_{1}$ depends on $a$ and $E$.

Define $\pi(x;d,a)$ to be the number of primes up to $x$ that belong to the
arithmetic progression $a$ mod $d$. Let $\mathcal{B}$ denote the set of
numbers $B$ in the range $0<B<1$ for which there is a number $x_{2}(B)$ and a
positive integer $D_{B}$ such that if $x\geq x_{2}(B)$, $(a,d)=1$ and $1\leq
d\leq\min\\{x^{B},y/x^{1-B}\\}$ then

(1.2) $\pi(y;d,a)\geq\frac{\pi(y)}{2\varphi(d)}$

whenever $d$ is not divisible by any member of $\mathcal{D}_{B}(x)$, a set of
at most $D_{B}$ integers, each of which exceeds $\log x$. We have
$(0,5/12)\subset\mathcal{B}$ (see [1]). The main theorem of this paper depends
intimately on the set $\mathcal{B}$.

######  Theorem 1.1.

For each $B\in\mathcal{B}$ and $E\in(0,1-(2\sqrt{e})^{-1})$, there is a number
$x_{0}=x_{0}(E,B)$ such that $C(x)\geq x^{EB}$ for all $x\geq x_{0}$.

Since $(0,5/12)\subset\mathcal{B}$, we have $C(x)>x^{\beta-\varepsilon}$ for
any $\varepsilon>0$ and all sufficiently large $x$, where

$\beta=\left(1-\frac{1}{2\sqrt{e}}\right)\times\frac{5}{12}=0.290306\cdots$

As mentioned above, we have $C(x)>x^{0.29}$ for all sufficiently large values
of $x$.

##  2\. Subsequence products representing the identity in a group

For a finite group $G$, let $n(G)$ denote the length of the longest sequence
of (not necessarily distinct) elements of $G$ for which no non-empty
subsequence has product the identity. Baker and Schmidt [2] gave an upper
bound for $n(G)$ for arbitrary finite abelian groups, which is

######  Theorem 2.1.

If $G$ is a finite abelian group and $m$ is the maximal order of an element in
$G$, then $n(G)<m(1+\log(|G|/m))$.

The idea is to construct an integer $L$ for which there are a very large
number of primes $p$ such that $p+1$ divides $L$. Suppose that the product of
some of these primes, say $C=p_{1}\cdots p_{k}$, is congruent to $1$ mod $L$,
then $C$ is a $(-1,1)$-Carmichael number by definition. If we view these
primes $p$ as elements of the group $G=(\mathbb{Z}/L\mathbb{Z})^{*}$, then the
condition becomes that, $C$ equals the identity of $G$. Though different
primes $p$ may map to the same element of $G$, we view them as different
elements of $G$, say label them with different numbers. The next result allows
us to construct many such products [1].

######  Theorem 2.2.

Let $G$ be a finite abelian group and let $r>t>n=n(G)$ be integers. Then any
sequence of $r$ elements of $G$ contains at least
$\left.\binom{r}{t}\right/\binom{r}{n}$ distinct subsequences of length at
most $t$ and at least $t-n$, whose product is the identity.

Let $R$ be a sequence of $r$ elements of $G$. Though $R$ may contain same
elements of $G$, we label these same elements with different numbers and view
them as different elements. The step is necessary since the original proof may
construct same subsequences, but we view them as different subsequences if
their elements has different labeled numbers.

For example, let $G=(\mathbb{Z}/5\mathbb{Z})^{*}$. We view $\\{19,29\\}$ and
$\\{19,59\\}$ as different subsequences of $G$, although they are $\\{4,4\\}$
in the reduced residue class mod $5$.

##  3\. Infinitude of (-1,1)-Carmichael numbers

First we prove a theorem resembling Theorem 3.1 of [1] and the proof is based
on that.

######  Theorem 3.1.

Suppose that $B\in\mathcal{B}$ and $a$ is a fixed non-zero integer. There
exists a number $x_{3}(B)$ such that if $x\geq x_{3}(B)$ and $L$ is a
squarefree integer not divisible by any prime exceeding $x^{(1-B)/2}$ and for
which $\sum_{\mathrm{prime}\ q|L}1/q\leq(1-B)/32$, then there is a positive
integer $k\leq x^{1-B}+|a|$ with $(k,aL)=1$, such that

$\\#\\{d|L:dk+a\leq x,\ dk+a\text{ is
prime}\\}\geq\frac{2^{-D_{B}-\omega(a)-3}}{\log x}\\#\\{d|L:1\leq d\leq
x^{B}\\},$

where $\omega(n)$ is the number of distinct prime factors of $|n|$.

###### Proof.

Let $x_{3}(B)=\max\\{x_{2}(B),17^{(1-B)^{-1}},|a|^{(1-B)^{-1}}\\}$. For each
$d\in\mathcal{D}_{B}(x)$ which divides $L$, we divide some prime factor of $d$
out from $L$. Furthermore, we divide all prime factors of $(a,L)$ out from
$L$, so as to obtain a number $L^{\prime}$ which is not divisible by any
number in $\mathcal{D}_{B}(x)$ and $(a,L^{\prime})=1$. Thus
$\omega(L^{\prime})\geq\omega(L)-D_{B}-\omega(a)$, and

(3.1) $\\#\\{d|L^{\prime}:1\leq d\leq y\\}\geq
2^{-D_{B}-\omega(a)}\\#\\{d|L:1\leq d\leq y\\}$

for any $y\geq 1$. To see this, think of a divisor $d^{\prime}$ of
$L^{\prime}$ as corresponding to a divisor $d$ of $L$ if and only if
$d^{\prime}$ divides $d$ and $d/d^{\prime}$ divides $L/L^{\prime}$. So if
$d\leq y$ then the corresponding $d^{\prime}$ is at most $y$. Moreover, for
any divisor $d^{\prime}$ of $L^{\prime}$, the number of divisors $d$ of $L$
which correspond to $d^{\prime}$ is at most the number of divisors of
$L/L^{\prime}$, which is at most $2^{D_{B}+\omega(a)}$.

From (1.2) we see that, for each divisor $d$ of $L^{\prime}$ with $1\leq d\leq
x^{B}$, we have

(3.2)
$\pi(dx^{1-B};d,a)\geq\frac{\pi(dx^{1-B})}{2\varphi(d)}\geq\frac{dx^{1-B}}{2\varphi(d)\log(dx^{1-B})}\geq\frac{dx^{1-B}}{2\varphi(d)\log
x},$

since $\pi(y)\geq y/\log y$ for all $y\geq 17$ (see [6]). Furthermore, since
any prime factor $q$ of $L$ is at most $x^{(1-B)/2}$, we can use Montgomery
and Vaughan’s explicit version of the Brun-Titchmarsh theorem [5], to get

$\pi(dx^{1-B};dq,a)\leq\frac{2dx^{1-B}}{\varphi(dq)\log(x^{1-B}/q)}\leq\frac{4}{\varphi(q)(1-B)}\frac{dx^{1-B}}{\varphi(d)\log
x}\leq\frac{8}{q(1-B)}\frac{dx^{1-B}}{\varphi(d)\log x}.$

Therefore, by (3.2), the number of primes $p\leq dx^{1-B}$ with $p\equiv a\
\left(\mathrm{mod}\ d\right)$ and $((p-a)/d,L)=1$ is at least

$\displaystyle\ \ \ \ \pi(dx^{1-B};d,a)-\sum_{\text{prime
}q|L}\pi(dx^{1-B};dq,a)$
$\displaystyle\geq\left(\frac{1}{2}-\frac{8}{1-B}\sum_{\text{prime
}q|L}\frac{1}{q}\right)\frac{dx^{1-B}}{\varphi(d)\log x}$
$\displaystyle\geq\frac{x^{1-B}}{4\log x}.$

Thus we have at least

$\frac{x^{1-B}}{4\log x}\\#\\{d|L^{\prime}:1\leq d\leq x^{B}\\}$

pairs $(p,d)$ where $p\leq dx^{1-B}$ is a prime, $p\equiv a\
\left(\mathrm{mod}\ d\right)$, $((p-a)/d,L)=1$, $d|L^{\prime}$ and $1\leq
d\leq x^{B}$. Each such pair $(p,d)$ corresponds to an integer $(p-a)/d$ that
is coprime to $L$ and

$\frac{p-a}{d}\leq x^{1-B}+\frac{|a|}{d}\leq x^{1-B}+|a|.$

Since $x^{1-B}\geq|a|$, there is at least one integer $k\leq x^{1-B}+|a|$ with
$(k,L)=1$ such that $k$ has at least

$\frac{x^{1-B}}{x^{1-B}+|a|}\frac{1}{4\log x}\\#\\{d|L^{\prime}:1\leq d\leq
x^{B}\\}\geq\frac{1}{8\log x}\\#\\{d|L^{\prime}:1\leq d\leq x^{B}\\}$

representations as $(p-a)/d$ with $(p,d)$ as above. Moreover, we have
$(a,d)=1$ since $(a,L^{\prime})=1$, so

$\left(\frac{p-a}{d},a\right)=(p-a,a)=(p,a).$

If $(p,a)=p$, then $a=p$ since $p\geq a$, which is a contradiction to the
condition $((p-a)/d,L)=1$. Thus for this integer $k$ we have $(k,a)=1$ and

$\displaystyle\ \ \ \ \\#\\{d|L:dk+a\leq x,\ dk+a\text{ is prime}\\}$
$\displaystyle\geq\frac{1}{8\log x}\\#\\{d|L^{\prime}:1\leq d\leq x^{B}\\}$
$\displaystyle\geq\frac{2^{-D_{B}-\omega(a)-3}}{\log x}\\#\\{d|L:1\leq d\leq
x^{B}\\},$

where we use (3.1) in the last inequality.

∎

Now we recalling the main theorem of this paper.

Theorem 1.1. For each $B\in\mathcal{B}$ and $E\in(0,1-(2\sqrt{e})^{-1})$,
there is a number $x_{0}=x_{0}(E,B)$ such that $C(x)\geq x^{EB}$ for all
$x\geq x_{0}$.

###### Proof.

Let $0<\varepsilon<EB$ be a fixed number, $\theta=(1-E)^{-1}$ and let $y\geq
2$ be a parameter. Denote by $\mathcal{Q}$ the set of primes
$q\in(y^{\theta}/\log y,y^{\theta}]$ for which $q-1$ is free of prime factors
exceeding $y$. By (1.1),

(3.3) $\displaystyle|\mathcal{Q}|$
$\displaystyle=\pi_{1}(y^{\theta},y)-\pi_{1}(y^{\theta}/\log y,y)$
$\displaystyle\geq\gamma(E)\frac{y^{\theta}}{\log
y^{\theta}}-\frac{2y^{\theta}}{(\log y)\log(y^{\theta}/\log y)}$
$\displaystyle\geq\frac{\gamma(E)}{2}\frac{y^{\theta}}{\log y^{\theta}}$

for all sufficiently large $y$. Let $L$ be the product of the primes
$q\in\mathcal{Q}$, then

(3.4) $\log L\leq|\mathcal{Q}|\log y^{\theta}\leq\pi(y^{\theta})\log
y^{\theta}\leq 2y^{\theta}$

for all sufficiently large $y$. Let $\lambda(n)$ denote the Carmichael lambda
function, the largest order of an element in $(\mathbb{Z}/n\mathbb{Z})^{*}$.
We have $\lambda(L)$ is the least common multiple of the numbers $q-1$ for
those primes $q$ that divide $L$. Since each such $q-1$ is free of prime
factors exceeding $y$, we know that if the prime power $p^{s}$ divides
$\lambda(L)$ then $p\leq y$ and $p^{s}\leq y^{\theta}$. Thus if we let
$p^{s_{p}}$ be the largest power of $p$ with $p^{s_{p}}\leq y^{\theta}$, then

(3.5) $\lambda(L)\leq\prod_{p\leq y}p^{a_{p}}\leq\prod_{p\leq
y}y^{\theta}=y^{\theta\pi(y)}\leq e^{2\theta y}$

for all sufficiently large $y$. Let $\delta=\varepsilon\theta/(4B)$ and let
$x=e^{y^{1+\delta}}$. By Theorem 5 of [6] we have

$\displaystyle\sum_{\text{prime }q|L}\frac{1}{q}$
$\displaystyle\leq\sum_{y^{\theta}/\log y<q\leq y^{\theta}}\frac{1}{q}$
$\displaystyle\leq\log\log y^{\theta}+\frac{1}{2(\log
y^{\theta})^{2}}-\log\log(y^{\theta}/\log y)+\frac{1}{2(\log(y^{\theta}/\log
y))^{2}}$ $\displaystyle=\log\frac{\theta\log y}{\theta\log y-\log\log
y}+\frac{1}{2(\log y^{\theta})^{2}}+\frac{1}{2(\log(y^{\theta}/\log y))^{2}}$
$\displaystyle\leq\frac{1-B}{32}$

for all sufficiently large $y$. Then we can apply Theorem 3.1 with $B$, $x$,
$L$. Thus for all sufficiently large $y$, there is an integer $k$ coprime to
$L$, for which the set $\mathcal{P}$ of primes $p\leq x$ with $p=dk-1$ for
some divisor $d$ of $L$, satisfies

(3.6) $|\mathcal{P}|\geq\frac{2^{-D_{B}-3}}{\log x}\\#\\{d|L:1\leq d\leq
x^{B}\\}.$

Let $G=(\mathbb{Z}/L\mathbb{Z})^{*}\times(\mathbb{Z}/2\mathbb{Z})^{+}$. Since
$\lambda(n)$ is even for all $n\in\mathbb{Z}_{\geq 3}$, we conclude from
Theorem 2.1, (3.4) and (3.5) that

(3.7)
$n(G)<\lambda(L)\left(1+\log\frac{2\varphi(L)}{\lambda(L)}\right)\leq\lambda(L)(1+\log
2+\log L)\leq e^{3\theta y}$

for all sufficiently large $y$. The product of any

$u:=\left\lfloor\frac{\log x^{B}}{\log
y^{\theta}}\right\rfloor=\left\lfloor\frac{B\log x}{\theta\log
y}\right\rfloor$

distinct prime factors of $L$, is a divisor $d$ of $L$ with $d\leq x^{B}$. We
deduce from (3.3) that

$\\#\\{d|L:1\leq d\leq
x^{B}\\}\geq\binom{\omega(L)}{u}\geq\left(\frac{\omega(L)}{u}\right)^{u}\geq\left(\frac{\gamma(E)y^{\theta}}{2B\log
x}\right)^{u}=\left(\frac{\gamma(E)}{2B}y^{\theta-1-\delta}\right)^{u}.$

Thus, by $\eqref{calP}$ and the identity
$(\theta-1-\delta)B/\theta=EB-\varepsilon/4$, we have

(3.8) $|\mathcal{P}|\geq\frac{2^{-D_{B}-3}}{\log
x}\left(\frac{\gamma(E)}{2B}y^{\theta-1-\delta}\right)^{\left\lfloor\frac{B\log
x}{\theta\log y}\right\rfloor}$

for all sufficiently large $y$. Now take
$\mathcal{P}^{\prime}=\mathcal{P}\backslash\mathcal{Q}$. Since
$|\mathcal{Q}|\leq y^{\theta}$, we have by (3.8) that

(3.9) $|\mathcal{P}^{\prime}|\geq x^{EB-\varepsilon/2}$

for all sufficiently large $y$.

For each element of $p\in\mathcal{P}^{\prime}$, we view it as the element
$(\overline{p},-1)\in G$, where $\overline{p}$ denotes the residue of $p$ in
$(\mathbb{Z}/L\mathbb{Z})^{*}$. As mentioned above, if
$\overline{p_{i}}=\overline{p_{j}}$ but $p_{i}\neq p_{j}$, then we view
$(\overline{p_{i}},-1)$ and $(\overline{p_{j}},-1)$ as two different elements
of $G$. If $\mathcal{S}$ is a subsequence of $G$ that contains more than one
element and if

$\Pi(\mathcal{S}):=\prod_{g\in\mathcal{S}}g=1_{G},$

then we can construct a $(-1,1)$-Carmichael number. Firstly, $|\mathcal{S}|$
must be even, since the second component of all elements are $-1$. Moreover,
the product of the first component of all elements is $1$ mod $L$, say

$\Pi_{1}(\mathcal{S}):=\prod_{p}p\equiv 1\ \left(\mathrm{mod}\ L\right),$

where the product is over all preimages of first component of elements in
$\mathcal{S}$. Furthermore, each member of $\mathcal{P}$ is $-1$ mod $k$ so
that $\Pi_{1}(\mathcal{S})\equiv 1\ \left(\mathrm{mod}\ k\right)$, since
$|\mathcal{S}|$ is even. Thus $\Pi_{1}(\mathcal{S})\equiv 1\
\left(\mathrm{mod}\ kL\right)$ since $(k,L)=1$. If $p\in\mathcal{P}^{\prime}$
then $p\in\mathcal{P}$ so that $p+1=kd\,|\,kL\,|\,\Pi_{1}(\mathcal{S})-1$.
Thus $\Pi_{1}(\mathcal{S})$ is a $(-1,1)$-Carmichael number.

Let $t=e^{y^{1+\delta/2}}$. Evidently $t>n(G)$ for all sufficiently large $y$.
Then by Theorem 2.2, we see that the number of $(-1,1)$-Carmichael numbers of
the form $\Pi_{1}(\mathcal{S})$, where $\left\lfloor
t\right\rfloor-n(G)\leq|\mathcal{S}|\leq\left\lfloor t\right\rfloor$, is at
least

$\left.\binom{|\mathcal{P}^{\prime}|}{\left\lfloor
t\right\rfloor}\right/\binom{|\mathcal{P}^{\prime}|}{n(G)}\geq\left.{\left(\frac{|\mathcal{P}^{\prime}|}{\left\lfloor
t\right\rfloor}\right)^{\left\lfloor
t\right\rfloor}}\right/|\mathcal{P}^{\prime}|^{n(G)}\geq\left(x^{EB-\varepsilon/2}\right)^{\left\lfloor
t\right\rfloor-n(G)}\left\lfloor t\right\rfloor^{-\left\lfloor
t\right\rfloor}\geq x^{t(EB-\varepsilon)}$

for all sufficiently large $y$, using $\eqref{n(G) upper bound}$ and
$\eqref{calP'}$. Since each $(-1,1)$-Carmichael number we construct satisfy
$\Pi_{1}(\mathcal{S})\leq x^{t}$, we have $C(X)\geq X^{EB-\varepsilon}$ for
all sufficiently large $y$, where $X:=x^{t}$. Moreover, since $y$ and $X$ can
be uniquely determined by each other, we derive $C(x)\geq x^{EB-\varepsilon}$
for each $B\in\mathcal{B}$, $E\in(0,1-(2\sqrt{e})^{-1})$, $0<\varepsilon<EB$
and sufficiently large $x$.

Since $E$ is in an open interval, choose $E^{\prime}\in(0,1-(2\sqrt{e})^{-1})$
with $E^{\prime}>E$ and let $\varepsilon=(E^{\prime}-E)B$, then we have
$C(x)\geq x^{E^{\prime}B-(E^{\prime}-E)B}=x^{EB}$ for sufficiently large $x$,
this completes the proof.

∎

Unfortunately, our proof is not applicable to the case $a\neq 1$. In fact, we
can only solve the case that $a$ have a small order mod $k$ (see Theorem 3.1).
Since the properties of $k$ is unknown, $k$ may ruin the estimate of some
arguments. Anyway, we believe that for non-zero integers $a$, $b$, there are
infinitely many $(a,b)$-Carmichael numbers.

## Acknowledgement

The ideas came to us after seeing the papers [1] and [8]. The method we used
in this paper is a simple modification of method in [1].

## References

  * [1] Alford W R, Granville A, Pomerance C. There are infinitely many Carmichael numbers[J]. Annals of Mathematics, 1994: 703-722.
  * [2] Baker R C, Schmidt W M. Diophantine problems in variables restricted to the values 0 and 1[J]. Journal of Number Theory, 1980, 12(4): 460-486.
  * [3] Friedlander J B. Shifted primes without large prime factors[J]. Number theory and applications, 1989: 393-401.
  * [4] Korselt A. Probleme chinois[J]. L’intermédiaire math, 1899, 6: 143-143.
  * [5] Montgomery H L, Vaughan R C. The large sieve[J]. Mathematika, 1973, 20(2): 119-134.
  * [6] Rosser J B, Schoenfeld L. Approximate formulas for some functions of prime numbers[J]. Illinois Journal of Mathematics, 1962, 6(1): 64-94.
  * [7] Sloane N J A. The on-line encyclopedia of integer sequences[M]//Towards mechanized mathematical assistants. Springer, Berlin, Heidelberg, 2007: 130-130.
  * [8] Wright T. There are infinitely many elliptic Carmichael numbers[J]. Bulletin of the London Mathematical Society, 2018, 50(5): 791-800.